On Friday October 17, this site was moved to a new server, https://mw.hh.se. The original address will continue to work. Whithin a week or two this site will return to the original address. /Peo HH IT-dep
WG211/M12Glück
From WG 2.11
Jump to navigationJump to search
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.
