Hierarchies of Turing machines with restricted tape alphabet size

DOI10.1016/S0022-0000(75)80049-3zbMATH Open0307.68037MaRDI QIDQ1218271FDOQ1218271

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

• On the Computational Complexity of Algorithms
• Title not available (Why is that?)
• Title not available (Why is that?)
• A Hierarchy Theorem for Polynomial-Space Recognition

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)