wiki_research

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

deterministic_k_turn_pushdown_automata_equivalence (330B)


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