Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
From MaRDI portal
Publication:2558752
DOI10.1016/S0022-0000(71)80029-6zbMath0255.68012OpenAlexW2010873193MaRDI QIDQ2558752
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
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
