Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata

DOI10.1007/978-3-642-04027-6_18zbMath1257.03063OpenAlexW2143407798MaRDI QIDQ3644751

Filip Murlak, Jacques Duparc, Alessandro Facchini

Publication date: 12 November 2009

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

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_18

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Decidability of theories and sets of sentences (03B25) Hierarchies of computability and definability (03D55)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hierarchies of weak automata and weak monadic formulas
• The Borel hierarchy is infinite in the class of regular sets of trees
• The modal mu-calculus alternation hierarchy is strict
• A hierarchy of deterministic context-free \(\omega\)-languages.
• A gap property of deterministic tree languages.
• Relating word and tree automata
• Wadge hierarchy and Veblen hierarchy Part I: Borel sets of finite rank
• Borel ranks and Wadge degrees of context free $\omega$-languages
• On ω-regular sets
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Weak index versus Borel rank
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• An automata-theoretic approach to branching-time model checking
• On the Borel Inseparability of Game Tree Languages
• Computer Science Logic
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Decision problems forω-automata
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The Wadge Hierarchy of Deterministic Tree Languages

This page was built for publication: Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata