Index Problems for Game Automata

DOI10.1145/2946800zbMath1367.68167arXiv1506.02153OpenAlexW2247132892MaRDI QIDQ5278187

Michał Skrzypczak, Filip Murlak, Alessandro Facchini

Publication date: 13 July 2017

Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1506.02153

zbMATH Keywords

parity gamesalternationRabin-Mostowski indexautomata over infinite trees

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Unnamed Item, A Characterisation of Pi^0_2 Regular Tree Languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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 monadic theory of order
• A gap property of deterministic tree languages.
• Ambiguous classes in \(\mu\)-calculi hierarchies
• Definable Operations On Weakly Recognizable Sets of Trees
• On the Weak Index Problem for Game Automata
• Regular Languages of Infinite Trees That Are Boolean Combinations of Open Sets
• On the Expressive Power of Cost Logics over Infinite Words
• The Non-deterministic Mostowski Hierarchy and Distance-Parity Automata
• Weak index versus Borel rank
• Deciding low levels of tree-automata hierarchy
• Theμ-calculus alternation-depth hierarchy is strict on binary trees
• Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata
• Computer Science Logic
• On the Topological Complexity of Weakly Recognizable Tree Languages
• Testing and generating infinite sequences by a finite automaton
• Decidability of Second-Order Theories and Automata on Infinite Trees
• The Wadge Hierarchy of Deterministic Tree Languages