Abstract FR:

On considère des jeux à deux joueurs sur des familles de graphes infinis. Notre but est de déterminer le gagnant et de calculer une stratégie gagnante. Nous avons considéré différentes conditions de gain : accessibilité, Büchi (récurrence), Sigma3, parité, et différentes classes de graphes depuis les graphes de transition des automates à pile jusqu'aux graphes de la hiérarchie de Caucal et aux automates à pile d'ordre supérieur. Deux types de méthodes ont été proposées : une approche symbolique fondée sur des automates finis, et des techniques de jeu-simulation. L'approche symbolique permet de représenter et de manipuler des ensembles infinis de configurations. La jeu-simulation consiste à réduire un jeu donné à un autre jeu plus simple que l'on sait résoudre, puis d'en déduire le gagnant et une stratégie gagnante dans le jeu initial. À chaque fois des algorithmes ont été donnés pour calculer le gagnant et une stratégie gagnante (à coup sûr).