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-6MaRDI QIDQ2558752zbMATH OpenOpenAlexFDO

Authors 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

• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• scientific article; zbMATH DE number 3363526 (Why is no real title available?)
• An Approach to a Unified Theory of Automata
• Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
• Checking automata and one-way stack languages
• Halting Stack Automata
• Nonerasing stack automata
• Relationships between nondeterministic and deterministic tape complexities
• Stack automata and compiling
• Two-Tape Simulation of Multitape Turing Machines
• Writing stack acceptors

Cited in

(26)

• Tradeoffs for language recognition on alternating machines
• Register Transducers Are Marble Transducers
• The power of two-way deterministic checking stack automata
• Stack languages and log n space
• New characterizations of exponential, elementary, and non-elementary time-bounded Turing machines
• Relating refined space complexity classes
• A relation between space, return and dual return complexities
• Alternating and empty alternating auxiliary stack automata.
• 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
• Iterated stack automata and complexity classes
• Tree-walking-storage automata
• Two-way nested stack automata are equivalent to two-way stack automata
• scientific article; zbMATH DE number 3808971 (Why is no real title available?)
• On Models of a Nondeterministic Computation
• scientific article; zbMATH DE number 3576701 (Why is no real title available?)
• Transducers of polynomial growth
• Hierarchies of one-way multihead automata languages
• Remarks on multihead pushdown automata and multihead stack automata
• Time complexity of languages recognized by one-way multihead pushdown automata
• Generalizations of Checking Stack Automata: Characterizations and Hierarchies
• 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)