Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 11 Décembre 2018

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

par Eric Duchêne (LIRIS, Lyon)

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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr