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

DOI10.1007/978-3-642-04027-6_18MaRDI QIDQ3644751zbMATH OpenOpenAlexFDO

Authors Jacques Duparc, Alessandro Facchini, Filip Murlak

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

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

Recommendations

• Index problems for game automata
• On the weak index problem for game automata
• Rabin-Mostowski index problem: a step beyond deterministic automata
• The Wadge Hierarchy of Deterministic Tree Languages
• The Wadge Hierarchy of Deterministic Tree Languages

Cites work

• A gap property of deterministic tree languages.
• A hierarchy of deterministic context-free \(\omega\)-languages.
• An automata-theoretic approach to branching-time model checking
• Borel ranks and Wadge degrees of context free \omega-languages
• Computer Science Logic
• Continuous separation of game languages
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Decision problems forω-automata
• Hierarchies of weak automata and weak monadic formulas
• scientific article; zbMATH DE number 3960988 (Why is no real title available?)
• scientific article; zbMATH DE number 3591916 (Why is no real title available?)
• scientific article; zbMATH DE number 1136070 (Why is no real title available?)
• scientific article; zbMATH DE number 1136080 (Why is no real title available?)
• On the Borel inseparability of game tree languages
• On the Topological Complexity of Weakly Recognizable Tree Languages
• On ω-regular sets
• Relating word and tree automata
• The Borel hierarchy is infinite in the class of regular sets of trees
• The modal mu-calculus alternation hierarchy is strict
• The Wadge Hierarchy of Deterministic Tree Languages
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Wadge Degrees ofω-Languages of Deterministic Turing Machines
• Wadge hierarchy and Veblen hierarchy. I: Borel sets of finite rank
• Weak index versus Borel rank

Cited in

(4)

• On the weak index problem for game automata
• Emptiness Of Alternating Tree Automata Using Games With Imperfect Information
• A Playful Glance at Hierarchical Questions for Two-Way Alternating Automata
• Index problems for game automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3644751)