WG211/M12Glück
From WG 2.11
Simulation of Two-Way Pushdown Automata Revisited by Robert Glück
We revisit a result from theoretical computer science from a programming language perspective. Cook's theorem (1972) showed that two-way deterministic pushdown automata (2DPDA) can be interpreted faster (in linear time) than they may run (in exponential time).
The essence of the result is explained using a semantics-based approach: we give a recursive interpreter which, when extended with random-access memory, performs a linear-time interpretation of 2DPDA. The construction is then extended to non-deterministic pushdown automata yielding a polynomial-time interpreter. The time required to run the final interpreter depends on the degree of nondeterminism of the automaton.
