zbMATH — the first resource for mathematics

On the weak index problem for game automata. (English) Zbl 06484971
Paiva, Valeria (ed.) et al., Logic, language, information, and computation. 22nd international workshop, WoLLIC 2015, Bloomington, IN, USA, July 20–23, 2015. Proceedings. Berlin: Springer (ISBN 978-3-662-47708-3/pbk; 978-3-662-47709-0/ebook). Lecture Notes in Computer Science 9160, 93-108 (2015).
Summary: 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.
For the entire collection see [Zbl 1319.03010].

03B70 Logic in computer science
Full Text: DOI