Index problems for game automata
From MaRDI portal
Abstract: For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognize this language with a non-deterministic, alternating, or weak alternating parity automaton. These questions are known as, respectively, the non-deterministic, alternating, and weak Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognizable by deterministic automata (the alternating variant trivializes). We investigate a wider class of regular languages, recognizable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognize languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy; that is, the alternating index problem does not trivialize any more. Our main contribution is that all three index problems are decidable for languages recognizable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognized by a game automaton.
Recommendations
- Rabin-Mostowski index problem: a step beyond deterministic automata
- On the weak index problem for game automata
- Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
- Unambiguous languages exhaust the index hierarchy
- Deciding low levels of tree-automata hierarchy
Cites work
- A gap property of deterministic tree languages.
- Ambiguous classes in \(\mu\)-calculi hierarchies
- Computer Science Logic
- Continuous separation of game languages
- Decidability of Second-Order Theories and Automata on Infinite Trees
- Deciding low levels of tree-automata hierarchy
- Deciding the weak definability of Büchi definable tree languages
- Definable operations on weakly recognizable sets of trees
- Hierarchies of weak automata and weak monadic formulas
- scientific article; zbMATH DE number 1670861 (Why is no real title available?)
- scientific article; zbMATH DE number 1304338 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (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?)
- scientific article; zbMATH DE number 1954388 (Why is no real title available?)
- scientific article; zbMATH DE number 3999901 (Why is no real title available?)
- On the Expressive Power of Cost Logics over Infinite Words
- On the Topological Complexity of Weakly Recognizable Tree Languages
- On the weak index problem for game automata
- Rabin-Mostowski index problem: a step beyond deterministic automata
- Regular languages of infinite trees that are Boolean combinations of open sets
- Testing and generating infinite sequences by a finite automaton
- The Borel hierarchy is infinite in the class of regular sets of trees
- The monadic theory of order
- The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
- The Wadge Hierarchy of Deterministic Tree Languages
- Theμ-calculus alternation-depth hierarchy is strict on binary trees
- Weak index versus Borel rank
Cited in
(8)- On the weak index problem for game automata
- Linear Game Automata: Decidable Hierarchy Problems for Stripped-Down Alternating Tree Automata
- Deciding low levels of tree-automata hierarchy
- A Characterisation of Pi^0_2 Regular Tree Languages
- Regular tree languages in low levels of the Wadge hierarchy
- Rabin-Mostowski index problem: a step beyond deterministic automata
- Computing the rabin index of a regular language of infinite words
- Deterministic and game separability for regular languages of infinite trees
This page was built for publication: Index problems for game automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5278187)
