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)

Mathematics Subject Classification ID

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

Cites work

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

Cited in

(7)

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

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)