Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata

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.