On space and time efficient TM simulations of some restricted classes of PDA's

DOI10.1016/S0019-9958(85)80030-9MaRDI QIDQ3716304zbMATH OpenFDO

Authors Oscar H. Ibarra, Sam M. Kim, Louis E. Rosier

Publication date 1985

Published in Information and Control (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0019-9958(85)80030-9

zbMATH Keywords

context-free languagesdeterministic pushdown automataspace/time efficient Turing machine algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 3907803
• scientific article; zbMATH DE number 4126702
• Simulation of two-way pushdown automata revisited
• The recognition of deterministic CFLs in small time and space
• On efficient deterministic simulation of turing machine computations below logaspace

Cited in

(4)

• On efficient recognition of transductions and relations
• Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
• scientific article; zbMATH DE number 3907803 (Why is no real title available?)
• scientific article; zbMATH DE number 4126702 (Why is no real title available?)

This page was built for publication: On space and time efficient TM simulations of some restricted classes of PDA's

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