wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

deterministic_k_turn_pushdown_automata_equivalence (391B)

      1 # Equivalence for Deterministic k turn pushdown automata
      2 
      3 - the [equivalence_problem] is [decidable]
      4   - cf [valiant1974decidability]
      5 - subsumed by [senizergues1997equivalence]
      6   - shows [decidability] of [DPDA_equivalence]
      7 
      8 Up: [language_equivalence_problem], [k_turn_pushdown_automata]
      9 
     10 Aliases: deterministic k turn PDA equivalence, equivalence for Deterministic k turn pushdown automata