WG211/M12Schultz

From WG 2.11
Revision as of 22:35, 26 March 2013 by Robert (talk | contribs) (Created page with "The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) is revisited. Following the semantics-based approach by Jones, a recursive interpreter is given which,...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) is revisited. Following the semantics-based approach by Jones, 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.

Retrieved from "https://wiki.hh.se/wg211/index.php?title=WG211/M12Schultz&oldid=766"