WG211/M12Schultz: Difference between revisions

Revision as of 23:35, 26 March 2013 view source Robert (talk \| contribs) 41 edits 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 23:36, 26 March 2013 view source Robert (talk \| contribs) 41 edits 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 23:36, 26 March 2013