Alternating automata, the weak monadic theory of trees and its complexity

DOI10.1016/0304-3975(92)90076-RzbMath0776.03017MaRDI QIDQ1193871

Paul E. Schupp, Ahmed Saoudi, David E. Muller

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)90076-r

zbMATH Keywords

alternating automata; automata on trees; alternations of quantifiers; weak monadic logic

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

03B25: Decidability of theories and sets of sentences

03D15: Complexity of computation (including implicit computational complexity)

Related Items

Unnamed Item, Theμ-calculus alternation-depth hierarchy is strict on binary trees, Converting a Büchi alternating automaton to a usual nondeterministic one, On mathematical contributions of Paul E. Schupp, Reachability is decidable for weakly extended process rewrite systems, \( \omega \)-automata, Automata on infinite trees, A focus system for the alternation-free \(\mu \)-calculus, On the separation question for tree languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The theory of ends, pushdown automata, and second-order logic
• Alternation and \(\omega\)-type Turing acceptors
• Alternating automata on infinite trees
• On alternating \(\omega\)-automata
• Alternation
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees