Generalized automata on infinite trees and Muller-McNaughton's theorem

DOI10.1016/0304-3975(91)90158-XzbMath0753.68070OpenAlexW2085563320MaRDI QIDQ1178688

Ahmed Saoudi

Publication date: 26 June 1992

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

Full work available at URL: https://doi.org/10.1016/0304-3975(91)90158-x

zbMATH Keywords

Boolean algebraautomata on treesMuller-McNaughton's theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Automata on infinite objects and their applications to logic and programming
• Infinitary tree languages recognized by \(\omega\)-automata
• Fundamental properties of infinite trees
• Determinacy of sinking automata on infinite trees and inequalities between various Rabin's pair indices
• Tree acceptors and some of their applications
• Pushdown tree automata
• Tree automata and attribute grammars
• A combinatorial approach to the theory of ω-automata
• Bottom-up and top-down tree transformations— a comparison
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item