On space-bounded synchronized alternating Turing machines

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

zbMATH Keywords

closure propertiesnondeterminismcomputational powerclasses of languages\(k\)-head finite automatadeterministic synchronized alternating finite automataoff-line capabilitysynchronized alternating Turing machines

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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