A hardest language recognized by two-way nondeterministic pushdown automata

DOI10.1016/0020-0190(81)90045-4zbMath0474.68089OpenAlexW2034634077MaRDI QIDQ1158974

Wojciech Rytter

Publication date: 1981

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(81)90045-4

zbMATH Keywords

language recognition

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Language recognition by two-way deterministic pushdown automata, Remarks on multihead pushdown automata and multihead stack automata

Cites Work

• On the existence of generators for certain AFL
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• The Hardest Context-Free Language