Characterizations of pushdown machines in terms of time-bounded computers

DOI10.1145/3588287.3588298MaRDI QIDQ6979511zbMATH OpenFDO

Authors Stephen Cook

Publication date 25 May 2025

Full work available at URL https://doi.org/10.1145/3588287.3588298

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20) First-order arithmetic and fragments (03F30) Computer science (68-XX) Theory of computing (68Qxx)

Cites work

• An efficient context-free parsing algorithm
• Computability of Recursive Functions
• scientific article; zbMATH DE number 3305097 (Why is no real title available?)
• Multi-tape and multi-head pushdown automata
• Nonerasing stack automata
• On the Computational Complexity of Algorithms
• Programming Language for Automata
• Stack automata and compiling
• Time and tape complexity of pushdown automaton languages
• Two-Tape Simulation of Multitape Turing Machines
• Two-way pushdown automata
• Variations on pushdown machines (Detailed Abstract)
• Writing pushdown acceptors

This page was built for publication: Characterizations of pushdown machines in terms of time-bounded computers

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