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: Difference between revisions
From WG 2.11
Jump to navigationJump to search
Created page with "''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 theo..." |
(No difference)
|
Latest revision as of 18:44, 28 May 2013
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.
