Alternating automata, the weak monadic theory of trees and its complexity
From MaRDI portal
Publication:1193871
DOI10.1016/0304-3975(92)90076-RzbMath0776.03017MaRDI QIDQ1193871
Paul E. Schupp, David E. Muller, Ahmed Saoudi
Publication date: 27 September 1992
Published in: Theoretical Computer Science (Search for Journal in Brave)
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
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, 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