Good-for-Games Automata
Denis Kuperberg
- 11:00 1st February 2017 ( week 3, Hilary Term 2017 )
Good-for-Games (GFG) automata are nondeterministic automata on infinite words, for which there is a strategy to resolve the non-determinism depending only on the prefix of the word read so far.
They offer an intermediate model between determinism and nondeterminism, retaining advantages from both sides. This makes them well suited tools for verification, for instance towards solving the Church Synthesis problem. After describing basic properties and examples, I will present recent results on this model. We focus on two particular problems: are GFG automata more succinct than deterministic ones, and what is the complexity of deciding whether an automaton is GFG ?
This is joint work with Michał Skrzypczak.
Speaker bio
Denis Kupferberg is a CNRS researcher in ENS Lyon, LIP. His main field is automata theory and verification, and he is also interested in quantitative models, links with logic and algebra, decidability and complexity properties.Share this:
