Hierarchies of Turing machines with restricted tape alphabet size

DOI10.1016/S0022-0000(75)80049-3zbMath0307.68037MaRDI QIDQ1218271

Sartaj K. Sahni, Oscar H. Ibarra

Publication date: 1975

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

Mathematics Subject Classification ID

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

Related Items

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

Cites Work

• Unnamed Item
• Unnamed Item
• A Hierarchy Theorem for Polynomial-Space Recognition
• On the Computational Complexity of Algorithms