Deterministic two-way one-head pushdown automata are very powerful
From MaRDI portal
Publication:800088
DOI10.1016/0020-0190(84)90001-2zbMath0549.68041OpenAlexW2017672035MaRDI QIDQ800088
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
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