January 5, 2015
Denis Kuperberg (IRIT/ONERA, Toulouse)Good-For-Games (GFG) automata are non-deterministic automata with a semantic condition that gives them some deterministic features: there must exist a strategy to resolve the non-determinism without future look-ahead, that allows to accept every word of the language. This notion was introduced in different contexts and several questions about its precise link with determinism were left open. The interest of these GFG automata stems from the fact that they can be used instead of deterministic ones in the context of games. For instance unlike general nondeterministic automata, GFG automata can be used in a sound way to evaluate the output of a game. It turns out that this new notion of GFG automata is only interesting over infinite words, since it boils down to determinism on finite words. After presenting examples of such GFG automata on infinite words, I will describe results on the blow-up problem, i.e. can we save states by replacing determinism by GFGness? This is joint work with Michał Skrzypczak.