Automates bons pour les jeux.
Denis Kuperberg  1, *@  
1 : LIP  (LIP)
CNRS : UMR5668
ENS de Lyon, -  France
* : Auteur correspondant

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.


Personnes connectées : 1