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

DOI10.1016/0304-3975(92)90076-RzbMath0776.03017OpenAlexW2087756506MaRDI 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 automataautomata on treesalternations of quantifiersweak monadic logic

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (9)

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

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

This page was built for publication: Alternating automata, the weak monadic theory of trees and its complexity