2026-07-24T01:59:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16458 2024-03-06T10:57:32Z ddc:004 open_access

On the Size of Good-For-Games Rabin Automata and Its Link with the Memory in Muller Games Casares, Antonio Colcombet, Thomas Lehtinen, Karoliina Infinite duration games Muller games Rabin conditions omega-regular languages memory in games good-for-games automata In this paper, we look at good-for-games Rabin automata that recognise a 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 that have this language as their winning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonio Casares and Thomas Colcombet and Karoliina Lehtinen 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.117 urn:nbn:de:0030-drops-164580 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.117 eng https://creativecommons.org/licenses/by/4.0/legalcode