Games and multidimensional shape-symmetric morphisms
2018
Online
Konferenz
Zugriff:
The general motivation behind this talk is to present some interplay between combinatorial game theory and combinatorics on multidimensional words. We do not assume that the participants have any prior knowledge in CGT. Thus, we will present some basic concepts from combinatorial game theory (positions of a game, Nim-sum, Sprague-Grundy function, Wythoff’s game, ...). We will see that games provide examples of k-automatic, morphic or k-regular sequences (in the sense of Allouche and Shallit). Subtraction games played on several piles of token naturally give rise to a multidimensional setting. Thus, we consider 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. The main part of this talk is to discuss the concept of shape-symmetric morphism introduced by Maes: 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 shape. We will present several decision problems which are decidable thanks to automata.
Titel: |
Games and multidimensional shape-symmetric morphisms
|
---|---|
Autor/in / Beteiligte Person: | Rigo, Michel |
Link: | |
Veröffentlichung: | 2018 |
Medientyp: | Konferenz |
Schlagwort: |
|
Sonstiges: |
|