Deterministic two-way one-head pushdown automata are very powerful

DOI10.1016/0020-0190(84)90001-2zbMath0549.68041OpenAlexW2017672035MaRDI QIDQ800088

Burkhard Monien

Publication date: 1984

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

Full work available at URL: http://nbn-resolving.de/urn:nbn:de:hbz:466:2-4388

zbMATH Keywords

complexity classesrandom access machinesone-letter alphabettwo-way pushdown automaton

Mathematics Subject Classification ID

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

Related Items (5)

Descriptional complexity of two-way pushdown automata with restricted head reversals ⋮ Investigations on Automata and Languages Over a Unary Alphabet ⋮ GENERALIZED COUNTERS AND REVERSAL COMPLEXITY ⋮ Interference automata ⋮ Language recognition by two-way deterministic pushdown automata

Cites Work

• Unnamed Item
• Fooling a two way automaton or one pushdown store is better than one counter for two way machines
• Transformational methods and their application to complexity problems. Corrigenda
• One way multihead deterministic finite automata
• On two-way multihead automata
• Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
• Separating Nondeterministic Time Complexity Classes
• k + 1 Heads Are Better than k
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers

This page was built for publication: Deterministic two-way one-head pushdown automata are very powerful