On the size of good-for-games Rabin automata and its link with the memory in Muller games

DOI10.4230/LIPICS.ICALP.2022.117MaRDI QIDQ6560918zbMATH OpenFDO

Authors Thomas Colcombet, Karoliina Lehtinen

Publication date 24 June 2024

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2022.117

zbMATH Keywords

good-for-games automatainfinite-duration gamesmemory in gamesMuller gamesomega-regular languagesRabin conditions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Applications of game theory (91A80)

Recommendations

• What kind of memory is needed to win infinitary Muller games?
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• On Determinisation of Good-for-Games Automata
• How deterministic are good-for-games automata?
• Büchi Good-for-Games Automata Are Efficiently Recognizable

Cited in

(8)

• Infinite separation between general and chromatic memory
• From Muller to parity and Rabin qutomata: optimal transformations preserving (history) determinism
• Half-positional objectives recognized by deterministic Büchi automata
• Symbolic solution of Emerson-Lei games for reactive synthesis
• Positional -regular languages
• Characterising memory in infinite games
• The complexity of simplifying -automata through the alternating cycle decomposition
• On the minimisation of deterministic and history-deterministic generalised (co)Büchi automata

This page was built for publication: On the size of good-for-games Rabin automata and its link with the memory in Muller games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6560918)