Alessandro Facchini, Filip Murlak and Michał Skrzypczak: On the Weak Index Problem for Game Automata

Game automata are known to recognise languages arbitrarily high in both the non-deterministic and alternating Rabin-Mostowski index hierarchies. Recently it was shown that for this class both hierarchies are decidable. Here we complete the picture by showing that the weak index hierarchy is decidable as well. We also provide a procedure computing for a game automaton an equivalent weak alternating automaton with the minimal index and a quadratic number of states. As a by-product we obtain that, as for deterministic automata, the weak index and the Borel rank coincide.