On Friday October 17, this site was moved to a new server, https://mw.hh.se. The original address will continue to work. Whithin a week or two this site will return to the original address. /Peo HH IT-dep
WG211/M12Glueck
From WG 2.11
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.
