Fooling a two way automaton or one pushdown store is better than one counter for two way machines
From MaRDI portal
Publication:1165027
DOI10.1016/0304-3975(82)90087-1zbMath0486.68084OpenAlexW2017429883MaRDI QIDQ1165027
Publication date: 1982
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(82)90087-1
Related Items (16)
String-matching cannot be done by a two-head one-way deterministic finite automaton ⋮ The equivalence of pebbles and sensing heads for finite automata ⋮ String matching with simple devices ⋮ Hierarchies of one-way multihead automata languages ⋮ Tradeoffs for language recognition on alternating machines ⋮ Lifting query complexity to time-space complexity for two-way finite automata ⋮ NON-RECURSIVE TRADE-OFFS FOR TWO-WAY MACHINES ⋮ A time-space tradeoff for language recognition ⋮ Combinatorial Lower Bound Arguments for Deterministic and Nondeterministic Turing Machines ⋮ GENERALIZED COUNTERS AND REVERSAL COMPLEXITY ⋮ On pure space vs catalytic space ⋮ Language recognition by two-way deterministic pushdown automata ⋮ On pure space vs catalytic space ⋮ Deterministic two-way one-head pushdown automata are very powerful ⋮ Variations on the technique of Ďuriš and Galil ⋮ Three one-way heads cannot do string matching
Cites Work
- Transformational methods and their application to complexity problems. Corrigenda
- On non-determinacy in simple computing devices
- On two-way multihead automata
- Two-Way Counter Machines and Diophantine Equations
- Some open problems in the theory of computation as questions about two-way deterministic pushdown automaton languages
- k + 1 Heads Are Better than k
- Nondeterminism and the size of two way finite automata
- Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Fooling a two way automaton or one pushdown store is better than one counter for two way machines
