Paper Info
Title
Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata
Abstract
For a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognise this language with a non-deterministic or alternating parity automaton. These questions are known as, respectively, the non-deterministic and the alternating Rabin-Mostowski index problems. Whether they can be answered effectively is a long-standing open problem, solved so far only for languages recognisable by deterministic automata (the alternating variant trivialises). We investigate a wider class of regular languages, recognisable by so-called game automata, which can be seen as the closure of deterministic ones under complementation and composition. Game automata are known to recognise languages arbitrarily high in the alternating Rabin-Mostowski index hierarchy, i.e., the alternating index problem does not trivialise any more. Our main contribution is that both index problems are decidable for languages recognisable by game automata. Additionally, we show that it is decidable whether a given regular language can be recognised by a game automaton.
Year
DOI
Venue
2013
10.1109/LICS.2013.56
LICS
Keywords
Field
DocType
parity automaton,deterministic automaton,game automaton,deterministic automata,long-standing open problem,so-called game automaton,rabin-mostowski index problem,rabin-mostowski index hierarchy,index problem,languages recognisable,regular language,indexes,games,automata,game theory,decidability,formal languages,nondeterministic
Quantum finite automata,Discrete mathematics,Two-way deterministic finite automaton,Automata theory,Combinatorics,Deterministic automaton,Nondeterministic finite automaton,Nested word,Computer science,Deterministic pushdown automaton,ω-automaton
Conference
ISSN
Citations 
PageRank 
1043-6871
8
0.69
References 
Authors
14
3
Name
Order
Citations
PageRank
Alessandro Facchini1359.47
Filip Murlak218419.14
Michal Skrzypczak32311.34