On the Weak Index Problem for Game Automata

Facchini, Alessandro and Murlak, Filip and Skrzypczak, Michal (2015) On the Weak Index Problem for Game Automata. In: Logic, Language, Information, and Computation WOLLIC 2015, Bloomington, Indiana .

Full text not available from this repository.


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.

Actions (login required)

View Item View Item