Difference between revisions of "WG211/M12Schultz"

Revision as of 22:35, 26 March 2013 (view source) 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,...")		Revision as of 22:36, 26 March 2013 (view source) Robert (talk \| contribs) (Blanked the page) Newer edit →
Line 1:		Line 1:
−	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.	+

Revision as of 22:36, 26 March 2013