WG211/M12Glueck
From WG 2.11
The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) is revisited. Following a semantics-based approach, a recursive interpreter is given which, when extended with random-access memory, performs a linear-time simulation of 2DPDA. The simulation is then extended to non-deterministic pushdown automata yielding a polynomial-time simulator. The constructions may provide an alternative angle to assess some program generation and complexity problems.
