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

generalizationpushdown automatonpartial memoization

Mathematics Subject Classification ID

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

• 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?)
• A note on linear time simulation of deterministic two-way pushdown automata
• Eliminating Redundant Recursive Calls.
• Fast Pattern Matching in Strings
• On the computational power of pushdown automata

Cited in

(3)

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

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)