Partial memoization for obtaining linear time behavior of a 2DPDA (Q1193887): Difference between revisions

\textit{S. A. Cook} [Inform. Processing 71, Proc. IFIP Congr. 71, Ljubljana, Yugoslavia 1971, 75-80 (1972; Zbl 0255.68015)] demonstrated the possibility of simulating any given 2-way Deterministic Pushdown Automaton (2DPDA) in linear time in the length of the read-only input tape. It is shown how this result can be obtained by means of a generalization of the well-known concept of memoization. This clever evaluation strategy will be termed partial memoization. A straight-forward simulator for two- way deterministic pushdown automata is presented, and it is shown that this simulator --- if memoization is performed on only a subset of its input parameters --- will run in linear time in the size of the tape input argument. Hence the idea of partial memoization provides a new and surprisingly simple proof of Cook's theorem.