Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
From MaRDI portal
Publication:3644751
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
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