Alternation and \(\omega\)-type Turing acceptors

DOI10.1016/0304-3975(86)90170-2zbMath0612.68074OpenAlexW2016312557MaRDI QIDQ1088417

Peter A. Lindsay

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90170-2

zbMATH Keywords

accepted language classesomega acceptors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Alternating automata on infinite trees ⋮ On alternating \(\omega\)-automata ⋮ Constructions for alternating finite automata^∗ ⋮ Alternating automata, the weak monadic theory of trees and its complexity

Cites Work

• Alternating finite automata on \(\omega\)-words
• On alternating \(\omega\)-automata
• On the complexity of \(\omega\)-type Turing acceptors
• Alternation and the Ackermann case of the decision problem
• Borel determinacy
• Alternation
• Decision problems forω-automata
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item