Unpublished conference/Abstract (Scientific congresses and symposiums)
Games and multidimensional shape-symmetric morphisms
Rigo, Michel
2018Workshop on Words and Complexity
 

Files


Full Text
Rigo.pdf
Author preprint (851.05 kB)
Beamer of the talk
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
words; morphism; game; combinatorics; Wythoff's game
Abstract :
[en] 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.
Disciplines :
Computer science
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Games and multidimensional shape-symmetric morphisms
Publication date :
19 February 2018
Event name :
Workshop on Words and Complexity
Event organizer :
University of Lyon
Event place :
Lyon, France
Event date :
from 19-02-2018 to 23-02-2018
By request :
Yes
Audience :
International
Available on ORBi :
since 17 February 2018

Statistics


Number of views
76 (7 by ULiège)
Number of downloads
35 (4 by ULiège)

Bibliography


Similar publications



Contact ORBi