2026-07-23T15:49:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:14192 2024-03-06T10:53:42Z ddc:004 open_access

Optimal Transformations of Games and Automata Using Muller Conditions Casares, Antonio Colcombet, Thomas Fijalkow, Nathanaël Automata over infinite words Omega regular languages Determinisation of automata We consider the following question: given an automaton or a game with a Muller condition, how can we efficiently construct an equivalent one with a parity condition? There are several examples of such transformations in the literature, including in the determinisation of Büchi automata. We define a new transformation called the alternating cycle decomposition, inspired and extending Zielonka’s construction. Our transformation operates on transition systems, encompassing both automata and games, and preserves semantic properties through the existence of a locally bijective morphism. We show a strong optimality result: the obtained parity transition system is minimal both in number of states and number of priorities with respect to locally bijective morphisms. We give two applications: the first is related to the determinisation of Büchi automata, and the second is to give crisp characterisations on the possibility of relabelling automata with different acceptance conditions. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Antonio Casares and Thomas Colcombet and Nathanaël Fijalkow 2021 Is Part Of LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2021.123 urn:nbn:de:0030-drops-141928 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.123 eng https://creativecommons.org/licenses/by/4.0/legalcode