Deterministic automata are more usable than nondeterministic automata in contexts such as synthesis because of their compositional properties. Unfortunately, determinization is complicated and involves an exponential increase in the state space for $\omega$-regular automata. Nondeterministic automata that are good for games have been heralded as a potential way to combine the compositionality of deterministic automata with the conciseness of nondeterministic ones. I am interested in how the benefits of good-for-games automata extend to alternating automata, and how good-for-games automata can be recognised.
-
Good for games automata: From nondeterminism to alternation with Udi Boker
-
On succinctness and recognisability of alternating good-for-games automata with Udi Boker, Denis Kuperberg, Karoliina Lehtinen, Michał Skrzypczak
Beyond $\omega$-regular automata, for which good-for-games automata can at best provide succinctness, I am interested in good-for-games pushdown automata: these automata are more expressive than deterministic ones, but problems like universality and synthesis are still decidable, unlike for their nondeterministic counterparts.
- Good-for-games $\omega$-pushdown automata with Martin Zimmermann