On space-bounded synchronized alternating Turing machines
From MaRDI portal
Publication:1193901
DOI10.1016/0304-3975(92)90351-FzbMath0773.68026OpenAlexW2018130813MaRDI QIDQ1193901
Oscar H. Ibarra, Nicholas Q. Tran
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(92)90351-f
closure propertiesnondeterminismcomputational powerclasses of languages\(k\)-head finite automatadeterministic synchronized alternating finite automataoff-line capabilitysynchronized alternating Turing machines
Related Items
On communication-bounded synchronized alternating finite automata ⋮ Synchronized finite automata and 2DFA reductions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A space-hierarchy result on two-dimensional alternating Turing machines with only universal states
- Alternating simple multihead finite automata
- Alternating multicounter machines with constant number of reversals
- On the power of alternation in automata theory
- Alternating on-line Turing machines with only universal states and small space bounds
- Some observations concerning alternating Turing machines using small space
- Alternating multihead finite automata
- An information-theoretic approach to time bounds for on-line computation
- Two-dimensional alternating turing machines with only universal states
- Nondeterministic Space is Closed under Complementation
- Alternation
- (Semi)alternating stack automata
- ALTERNATING TURING MACHINES WITH MODIFIED ACCEPTING STRUCTURE
- k + 1 Heads Are Better than k
