Difference between revisions of "WG211/M12Glueck"
From WG 2.11
(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,...") |
|||
| Line 1: | Line 1: | ||
| − | The linear-time simulation of 2-way deterministic pushdown automata (2DPDA) is revisited. Following | + | 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. |
Latest revision as of 22:38, 26 March 2013
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.
