WG211/M12Glück

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.