Multi angle

H 1 From combinatorial games to shape-symmetric morphisms

Auteurs : Rigo, Michel (Auteur de la Conférence)
CIRM (Editeur )

    Loading the player...

    Résumé : The general aim of these lectures is to present some interplay between combinatorial game theory (CGT) and combinatorics on (multidimensional) words.
    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.

    Codes MSC :
    68Q45 - Formal languages and automata
    68R15 - Combinatorics on words
    91A46 - Combinatorial games

      Informations sur la Vidéo

      Langue : Anglais
      Date de publication : 28/11/2017
      Date de captation : 21/11/2017
      Collection : Research schools ; Combinatorics ; Computer Science ; Number Theory
      Format : MP4
      Durée : 01:28:30
      Domaine : Computer Science ; Combinatorics ; Number Theory
      Audience : Chercheurs ; Etudiants Science Cycle 2 ; Doctorants , Post - Doctorants
      Download : https://videos.cirm-math.fr/2017-11-21_Rigo.mp4

    Informations sur la rencontre

    Nom de la rencontre : Jean-Morlet chair - Research school: Tiling dynamical system / Chaire Jean-Morlet - École de recherche : Pavages et systèmes dynamiques
    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

    Citation Data

    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

    Voir aussi


Titres de périodiques et e-books électroniques (Depuis le CIRM)

Ressources Electroniques

Books & Print journals

Recherche avancée