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-6zbMATH Open0255.68012OpenAlexW2010873193MaRDI QIDQ2558752FDOQ2558752

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

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

Cites Work

• Relationships between nondeterministic and deterministic tape complexities
• Title not available (Why is that?)
• Title not available (Why is that?)
• Two-Tape Simulation of Multitape Turing Machines
• Stack automata and compiling
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• An Approach to a Unified Theory of Automata
• Checking automata and one-way stack languages
• Nonerasing stack automata
• Writing stack acceptors
• Halting Stack Automata

Cited In (26)

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

This page was built for publication: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata

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