Generalizing Cook's transformation to imperative stack programs

DOI10.1007/3-540-58131-6_33MaRDI QIDQ6142866zbMATH OpenOpenAlexWikidataFDO

Authors

Publication date 29 January 2024

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-58131-6_33

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Classical models of computation (Turing machines, etc.) (68Q04) Formal languages and automata (68Q45)

Recommendations

• Partial memoization for obtaining linear time behavior of a 2DPDA
• scientific article; zbMATH DE number 1543035
• Simulation of two-way pushdown automata revisited
• scientific article; zbMATH DE number 4041248
• On reducing the number of stack symbols in a PDA

Cites work

• A note on linear time simulation of deterministic two-way pushdown automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• scientific article; zbMATH DE number 4101166 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 236855 (Why is no real title available?)
• scientific article; zbMATH DE number 3403734 (Why is no real title available?)
• Improving programs by the introduction of recursion
• Nondeterministic Algorithms

This page was built for publication: Generalizing Cook's transformation to imperative stack programs

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