Taking and merging games as rewrite games
Aline Parreau, Eric Duchêne
LIRIS, Université Lyon 1
https://perso.liris.cnrs.fr/aline.parreau/
https://perso.liris.cnrs.fr/eric.duchene/
Date(s) : 27/02/2023 iCal
15h00 - 16h00
In this talk, we present some of the links between combinatorial games and language theory. A combinatorial game is a 2-player game with no chance and with perfect information. Amongst them, the family of heap games such as the game of Nim, subtraction or octal games belong to the the most studied ones. Generally, the analysis of such games consist in determining which player has a winning strategy. We will first see how this question is investigated in the case of heap games.
In a second part of the talk, we will present a generalization of heap games as rewrite games on words. This model was introduced by Waldmann in 2002. Given a finite alphabet and a set of rewriting rules on it, starting from a finite word w, each player alternately applies a rule on w. The first player unable to apply a rule loses the game. In this context, the main question is now about the class of the language formed by the losing and winning positions of the game. For example, for octal games that are solved in polynomial time, the losing positions form a rational language. By using the model of rewrite games, we will investigate here a new family of heap games that consist in merging heaps of tokens, and consider some of the different classes of languages that may emerge according to the rules of the game.
(joint work with V. Marsault and M. Rigo)
The address of the Zoom meeting is https://zoom.us/j/92245493528 . The password is distributed in announcements. If you want to receive them, or receive them and want to unsubscribe, please write to Anna Frid.
More info: https://www.i2m.univ-amu.fr/wiki/Combinatorics-on-Words-seminar/
Emplacement
Virtual event
Catégories Pas de Catégories
