Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata

DOI10.1016/S0022-0000(71)80029-6zbMath0255.68012OpenAlexW2010873193MaRDI QIDQ2558752

Oscar H. Ibarra

Publication date: 1971

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(71)80029-6

Mathematics Subject Classification ID

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

Related Items

Alternating and empty alternating auxiliary stack automata., Two-way automata with more than one storage medium, On pebble automata, Hierarchies of one-way multihead automata languages, Unnamed Item, Tradeoffs for language recognition on alternating machines, On regular realizability problems, New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines, Tree-walking-storage automata, Generalizations of Checking Stack Automata: Characterizations and Hierarchies, Time complexity of languages recognized by one-way multihead pushdown automata, Unnamed Item, Iterated stack automata and complexity classes, On the complexity of finite, pushdown, and stack automata, Two-way nested stack automata are equivalent to two-way stack automata, Relating refined space complexity classes, Stack languages and log n space, A relation between space, return and dual return complexities, The power of two-way deterministic checking stack automata, Register Transducers Are Marble Transducers, On Models of a Nondeterministic Computation, On two-way multihead automata, Remarks on multihead pushdown automata and multihead stack automata, On efficient recognition of transductions and relations, (Semi)alternating stack automata

Cites Work

• Unnamed Item
• Unnamed Item
• Nonerasing stack automata
• Checking automata and one-way stack languages
• Relationships between nondeterministic and deterministic tape complexities
• Writing stack acceptors
• Two-Tape Simulation of Multitape Turing Machines
• Stack automata and compiling
• An Approach to a Unified Theory of Automata
• Halting Stack Automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers