Hierarchies of Turing machines with restricted tape alphabet size

DOI10.1016/S0022-0000(75)80049-3MaRDI QIDQ1218271zbMATH OpenFDO

Authors Oscar H. Ibarra, Sartaj Sahni

Publication date 1975

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0022-0000(75)80049-3

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• A Hierarchy Theorem for Polynomial-Space Recognition
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• On the Computational Complexity of Algorithms

Cited in

(7)

• Complexity lower bounds for machine computing models
• Hierarchy of complexity of computation of partial functions with values 0 and 1
• Techniques for separating space complexity classes
• Relating refined space complexity classes
• Two-dimensional finite automata and unacceptable functions
• Two-way automata and length-preserving homomorphisms
• Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs

This page was built for publication: Hierarchies of Turing machines with restricted tape alphabet size

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