Les jeux de réécriture: une passerelle entre théorie des jeux combinatoires et théorie des langages

Cet exposé présente certains liens qui existent entre les jeux combinatoires et la théorie des langages. Un jeu combinatoire est un jeu à deux joueurs, sans hasard, à information parfaite. Parmi les jeux les plus étudiés dans la littérature, on trouve les jeux de suppression de jetons dans des piles comme le jeu de Nim, les jeux de soustraction ou les jeux octaux. Bien souvent, l’étude d’un tel jeu consiste à calculer la complexité algorithmique d’une stratégie gagnante pour l’un des deux joueurs. Dans le cas des jeux de jetons, nous verrons tout d’abord comment cette question est abordée dans la littérature.

Par la suite, nous présenterons une généralisation des jeux de jetons sous forme de jeux de réécriture sur des mots. Ce modèle a été introduit par Waldmann en 2002. Dans ce contexte, l’objet d’intérêt devient la classe de langage formée par les positions perdantes et gagnantes jeu. Par exemple, pour les jeux octaux résolus en temps polynomial, le langage des positions perdantes est rationnel. On s’intéressera ici à une nouvelle famille de jeux de réécriture correspondant à fusionner des piles de jetons, et nous verrons les différents langages qui peuvent émerger en fonction des règles du jeu de réécriture.