Loading the player...
The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.
Codes MSC :
In the first introductory lecture, we present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We also review some concepts from combinatorics on words. We thus introduce the well-known k-automatic sequences and review some of their characterizations (in terms of morphisms, finiteness of their k-kernel,...). These sequences take values in a finite set but the Sprague-Grundy function of a game, such as Nim of Wythoff, is usually unbounded. This provides a motivation to introduce k-regular sequences (in the sense of Allouche and Shallit) whose k-kernel is not finite, but finitely generated.
In the second lecture, games played on several piles of token naturally give rise to a multi-dimensional setting. Thus, we reconsider k-automatic and k-regular sequences in this extended framework. In particular, determining the structure of the bidimensional array encoding the (loosing) P-positions of the Wythoff’s game is a long-standing and challenging problem in CGT. Wythoff’s game is linked to non-standard numeration system: P-positions can be determined by writing those in the Fibonacci system. Next, we present the concept of shape-symmetric morphism: instead of iterating a morphism where images of letters are (hyper-)cubes of a fixed length k, one can generalize the procedure to images of various parallelepipedic shape. The shape-symmetry condition introduced twenty years ago by Maes permits to have well-defined fixed point.
In the last lecture, we move to generalized numeration systems: abstract numeration systems (built on a regular language) and link them to morphic (multidimensional) words. In particular, pictures obtained by shape-symmetric morphisms coincide with automatic sequences associated with an abstract numeration system. We conclude these lectures with some work in progress about games with a finite rule-set. This permits us to discuss a bit Presburger definable sets.
- Formal languages and automata
- Combinatorics on words
- Combinatorial games
Nom de la rencontre : Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques
Informations sur la rencontre
Organisateurs de la rencontre : Akiyama, Shigeki ; Arnoux, Pierre
Dates : 20/11/2017 - 24/11/2017
Année de la rencontre : 2017
URL Congrès : https://akiyama-arnoux.weebly.com/school.html
DOI : 10.24350/CIRM.V.19249403
Cite this video as:
Rigo, Michel (2017). From combinatorial games to shape-symmetric morphisms. CIRM. Audiovisual resource. doi:10.24350/CIRM.V.19249403
URI : http://dx.doi.org/10.24350/CIRM.V.19249403