Automates bons pour les jeux.
1 : LIP
(LIP)
* : Auteur correspondant
CNRS : UMR5668
ENS de Lyon, -
France
Un automate sur mots infinis est dit Good-for-Game (GFG) s'il existe une stratégie pour résoudre les choix non-déterministes au fur et à mesure de la lecture du mot d'entrée, sans avoir à deviner le futur. Ceci peut être vu comme un compromis entre déterminisme et non-déterminisme, qui préserve certains avantages des deux mondes. Comme les automates déterministes, on peut les composer avec des jeux ou des arbres en préservant leur sémantique. Mais comme les automates non-déterministes, ils peuvent être exponentiellement plus succincts que tout déterministe équivalent. Je présenterai les principaux résultats obtenus sur ces automates GFG, ainsi que certaines des recherches en cours.