On the equivalence of two-way pushdown automata and counter machines over bounded languages
- 1 January 1993
- book chapter
- Published by Springer Nature
- p. 354-364
- https://doi.org/10.1007/3-540-56503-5_36
Abstract
No abstract availableKeywords
This publication has 9 references indexed in Scilit:
- The Power of Alternating One-Reversal Counters and StacksSIAM Journal on Computing, 1991
- A note on bounded-reversal multipushdown machinesInformation Processing Letters, 1984
- Deterministic two-way one-head pushdown automata are very powerfulInformation Processing Letters, 1984
- Fooling a two way automation or one pushdown store is better than one counter for two way machinesTheoretical Computer Science, 1982
- Two-Way Counter Machines and Diophantine EquationsJournal of the ACM, 1982
- Simple counter machines and number-theoretic problemsJournal of Computer and System Sciences, 1979
- Reversal-Bounded Multicounter Machines and Their Decision ProblemsJournal of the ACM, 1978
- The equivalence problem for deterministic finite-turn pushdown automataInformation and Control, 1974
- Recursive Unsolvability of Post's Problem of "Tag" and other Topics in Theory of Turing MachinesAnnals of Mathematics, 1961