http://mw.hh.se/wg211/index.php?action=history&feed=atom&title=WG211%2FM12Gl%C3%BCck 2026-04-05T22:52:29Z Revision history for this page on the wiki MediaWiki 1.43.5 http://mw.hh.se/wg211/index.php?title=WG211/M12Gl%C3%BCck&diff=823&oldid=prev 2013-05-28T17:44:38Z

<p>Created page with &quot;&#039;&#039;Simulation of Two-Way Pushdown Automata Revisited&#039;&#039; by Robert Glück We revisit a result from theoretical computer science from a programming language perspective. Cook&#039;s theo...&quot;</p> <p><b>New page</b></p><div>&#039;&#039;Simulation of Two-Way Pushdown Automata Revisited&#039;&#039; by Robert Glück<br /> <br /> We revisit a result from theoretical computer science from a programming language perspective. Cook&#039;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).<br /> <br /> 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.</div>

Ups