On the Size of Good-for-games Rabin Automata and its Link with the Memory in Muller Games

In this work, we look at good-for-games Rabin automata that recognise a given Muller language (a language that is entirely characterised by the set of letters that appear infinitely often in each word). We establish that minimal such automata are exactly of the same size as the minimal memory required for winning Muller games with this condition. We show how to effectively construct such minimal automata. Finally, we establish that these automata can be exponentially more succinct than equivalent deterministic ones, thus proving as a consequence that chromatic memory for winning a Muller game can be exponentially larger than unconstrained memory. This is joint work with Thomas Colcombet and Karoliina Lehtinen.

Authors

• Antonio Casares

Keywords

No keywords are indexed for this paper.