Partial memoization for obtaining linear time behavior of a 2DPDA

DOI10.1016/0304-3975(92)90008-4MaRDI QIDQ1193887zbMATH OpenOpenAlexFDO

Authors Torben Amtoft, Jesper Larsson Träff

Publication date 27 September 1992

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(92)90008-4

zbMATH Keywords

generalizationpartial memoizationpushdown automaton

Mathematics Subject Classification ID

Review text

\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.

Recommendations

• Linear Time and Memory-Efficient Computation
• A bounds inference method for vector-based memoization
• Verified memoization and dynamic programming
• A linear time complexity of breadth-first search using P system with membrane division
• scientific article; zbMATH DE number 1953309
• A linear in memory non-exhaustive algorithm to solve a two-dimensional interval search problem
• On sharing, memoization, and polynomial time
• On sharing, memoization, and polynomial time
• scientific article; zbMATH DE number 4204219
• Dynamic programming in faulty memory hierarchies (cache-obliviously)

Cites work

• A note on linear time simulation of deterministic two-way pushdown automata
• Eliminating Redundant Recursive Calls.
• Fast Pattern Matching in Strings
• scientific article; zbMATH DE number 4101166 (Why is no real title available?)
• scientific article; zbMATH DE number 3731318 (Why is no real title available?)
• scientific article; zbMATH DE number 3403734 (Why is no real title available?)
• On the computational power of pushdown automata

Cited in

(3)

• scientific article; zbMATH DE number 1543035 (Why is no real title available?)
• Simulation of two-way pushdown automata revisited
• Generalizing Cook's transformation to imperative stack programs

This page was built for publication: Partial memoization for obtaining linear time behavior of a 2DPDA

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1193887)