Simulation of Two-Way Pushdown Automata Revisited
Open Access
- 19 September 2013
- journal article
- Published by Open Publishing Association in Electronic Proceedings in Theoretical Computer Science
- Vol. 129, 250-258
- https://doi.org/10.4204/eptcs.129.15
Abstract
The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) by the Cook and Jones constructions is revisited. Following the semantics-based approach by Jones, an interpreter is given which, when extended with random-access memory, performs a linear-time simulation of 2DPDA. The recursive interpreter works without the dump list of the original constructions, which makes Cook's insight into linear-time simulation of exponential-time automata more intuitive and the complexity argument clearer. The simulation is then extended to 2-way nondeterministic pushdown automata (2NPDA) to provide for a cubic-time recognition of context-free languages. The time required to run the final construction depends on the degree of nondeterminism. The key mechanism that enables the polynomial-time simulations is the sharing of computations by memoization.Comment: In Proceedings Festschrift for Dave Schmidt, arXiv:1309.455This publication has 8 references indexed in Scilit:
- Computability and ComplexityPublished by MIT Press ,1997
- WORM-2DPDAs: An extension to 2DPDAs that can be simulated in linear timeInformation Processing Letters, 1994
- Generalizing Cook's transformation to imperative stack programsPublished by Springer Science and Business Media LLC ,1994
- Partial memoization for obtaining linear time behavior of a 2DPDATheoretical Computer Science, 1992
- A note on linear time simulation of deterministic two-way pushdown automataInformation Processing Letters, 1977
- Fast Pattern Matching in StringsSIAM Journal on Computing, 1977
- Time and tape complexity of pushdown automaton languagesInformation and Control, 1968
- “Memo” Functions and Machine LearningNature, 1968