Publications of Michel Rigo  From combinatorial games to shape-symmetric morphismsRigo, Michel in Akiyama, Shigeki; Arnoux, Pierre (Eds.) Tiling Dynamical Systems (in press)Siegel suggests in his book on combinatorial games that quite simple games provide us with challenging problems: ``No general formula is known for computing arbitrary Grundy values of Wythoff's game. In ... [more ▼]Siegel suggests in his book on combinatorial games that quite simple games provide us with challenging problems: ``No general formula is known for computing arbitrary Grundy values of Wythoff's game. In general, they appear chaotic, though they exhibit a striking fractal-like pattern.''. This observation is the first motivation behind this chapter. We present some of the existing connections between combinatorial game theory and combinatorics on words. In particular, multidimensional infinite words can be seen as tiling of \$N^d\$. They naturally arise from subtraction games on \$d\$ heaps of tokens. We review notions such as \$k\$-automatic, \$k\$-regular or shape-symmetric multidimensional words. The underlying general idea is to associate a finite automaton with a morphism. [less ▲]Detailed reference viewed: 34 (8 ULiège) On Cobham's theoremDurand, Fabien; Rigo, Michel in Handbook of Automata (in press)Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 ... [more ▼]Let k >= 2 be an integer. A set X of integers is k-recognizable if the language of k-ary representations of the elements in X is accepted by a finite automaton. The celebrated theorem of Cobham from 1969 states that if a set of integers is both k-recognizable and ℓ-recognizable, then it is a finite union of arithmetic progressions. We present several extensions of this result to nonstandard numeration systems, we describe the relationships with substitutive and automatic words and list Cobham-type results in various contexts. [less ▲]Detailed reference viewed: 245 (33 ULiège) Templates for the k-binomial complexity of the Tribonacci wordLejeune, Marie ; Rigo, Michel ; Rosenfeld, Matthieu E-print/Working paper (2019)Consider the k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an ... [more ▼]Consider the k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word x maps the integer n to the number of pairwise non-equivalent factors of length n occurring in x. In this paper based on the notion of template introduced by Currie et al., we show that, for all k > 1, the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity p(n)=2n+1. A similar result was already known for Sturmian words but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci. [less ▲]Detailed reference viewed: 32 (7 ULiège) Automatic sequences based on Parry or Bertrand numeration systemsMassuir, Adeline ; Peltomäki, Jarkko; Rigo, Michel in Advances in Applied Mathematics (2019), 108We study the factor complexity and closure properties of automatic sequences based on Parry or Bertrand numeration systems. These automatic sequences can be viewed as generalizations of the more typical k ... [more ▼]We study the factor complexity and closure properties of automatic sequences based on Parry or Bertrand numeration systems. These automatic sequences can be viewed as generalizations of the more typical k-automatic sequences and Pisot-automatic sequences. We show that, like k-automatic sequences, Parry-automatic sequences have sublinear factor complexity while there exist Bertrand-automatic sequences with superlinear factor complexity. We prove that the set of Parry-automatic sequences with respect to a fixed Parry numeration system is not closed under taking images by uniform substitutions or periodic deletion of letters. These closure properties hold for k-automatic sequences and Pisot-automatic sequences, so our result shows that these properties are lost when generalizing to Parry numeration systems and beyond. Moreover, we show that a multidimensional sequence is U -automatic with respect to a positional numeration system U with regular language of numeration if and only if its U -kernel is finite. [less ▲]Detailed reference viewed: 21 (2 ULiège) Combinatoire des mots : résultats classiques et avancées récentesRigo, Michel Scientific conference (2018, April 19)Dans cet exposé ne nécessitant aucun prérequis, je présenterai quelques grands thèmes issus de la combinatoire des mots (i.e., des suites prenant leurs valeurs dans un ensemble fini de symboles) et leurs ... [more ▼]Dans cet exposé ne nécessitant aucun prérequis, je présenterai quelques grands thèmes issus de la combinatoire des mots (i.e., des suites prenant leurs valeurs dans un ensemble fini de symboles) et leurs possibles applications en théorie des nombres, en dynamique symbolique ou en géométrie discrète. En guise d'illustration, considérons le problème suivant. Un carré est la répétition de deux facteurs consécutifs identiques. Ainsi, le mot "entente" débute par le carré (ent)^2 et se aussi termine par le carré (nte)^2. Etant donné un alphabet de taille fixée, on souhaite construire un mot, le plus long possible, évitant un motif particulier. On se rend aisément compte qu'avec deux lettres, tout mot de longueur au moins 4 contient un carré. Par contre, il est possible de définir une suite infinie, à valeurs dans {0,1,2}, ne contenant aucun carré. Ces questions centrales d'évitabilité se retrouvent, dès le début du XXe siècle, dans les travaux d'Axel Thue et ont de multiples déclinaisons récentes. Dans un second temps, je me concentrerai sur une large famille de mots infinis, les suites k-automatiques. Elles sont obtenues à partir d'écritures en base entière k et d'un modèle de calcul des plus simples: un automate fini déterministe. On dispose alors d'une caractérisation logique de ces suites donnée par le théorème de Büchi. Dans ce cadre, de nombreux problèmes de nature combinatoire peuvent être décidés formellement de façon automatique. Nous montrerons les avantages de cette approche mais aussi ses limites. [less ▲]Detailed reference viewed: 28 (4 ULiège) Games and multidimensional shape-symmetric morphismsRigo, Michel Conference (2018, February 19)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 ... [more ▼]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. [less ▲]Detailed reference viewed: 48 (3 ULiège) Counting Subwords Occurrences in Base-b ExpansionsLeroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Integers: Electronic Journal of Combinatorial Number Theory (2018), 18AWe consider the sequence (Sb(n))n≥0 counting the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. By using a convenient tree structure, we provide ... [more ▼]We consider the sequence (Sb(n))n≥0 counting the number of distinct (scattered) subwords occurring in the base-b expansion of the non-negative integers. By using a convenient tree structure, we provide recurrence relations for (Sb(n))n≥0 leading to the b-regularity of the latter sequence. Then we deduce the asymptotics of the summatory function of the sequence (Sb(n))n≥0. [less ▲]Detailed reference viewed: 68 (22 ULiège) Sequences, Groups, and Number TheoryBerthé, Valérie; Rigo, Michel Book published by Birkhäuser (2018)This collaborative book presents recent trends on the study of sequences, including combinatorics on words and symbolic dynamics, and new interdisciplinary links to group theory and number theory. Other ... [more ▼]This collaborative book presents recent trends on the study of sequences, including combinatorics on words and symbolic dynamics, and new interdisciplinary links to group theory and number theory. Other chapters branch out from those areas into subfields of theoretical computer science, such as complexity theory and theory of automata. The book is built around four general themes: number theory and sequences, word combinatorics, normal numbers, and group theory. Those topics are rounded out by investigations into automatic and regular sequences, tilings and theory of computation, discrete dynamical systems, ergodic theory, numeration systems, automaton semigroups, and amenable groups. This volume is intended for use by graduate students or research mathematicians, as well as computer scientists who are working in automata theory and formal language theory. With its organization around unified themes, it would also be appropriate as a supplemental text for graduate level courses. [less ▲]Detailed reference viewed: 21 (5 ULiège) General frameworkBerthé, V.; Rigo, Michel in Berthé, Valérie; Rigo, Michel (Eds.) Sequences, Group and Number Theory (2018)This introductory chapter briefly presents some of the main notions that appear in the subsequent chapters of this book. We recap a few definitions and results from combinatorics on groups and words ... [more ▼]This introductory chapter briefly presents some of the main notions that appear in the subsequent chapters of this book. We recap a few definitions and results from combinatorics on groups and words, formal language theory, morphic words, k-automatic and k-regular sequences, and dynamical systems. Our aim is not to be exhaustive. The reader can consult this chapter when studying other parts of this book. © Springer International Publishing AG, part of Springer Nature 2018. [less ▲]Detailed reference viewed: 16 (1 ULiège) Les origines des systèmes de numération abstraits (avec un brin de nostalgie)Rigo, Michel Scientific conference (2017, December 19)Le but de cet exposé sera de retracer une partie des contributions de Pierre Lecomte en nformatique théorique.Detailed reference viewed: 51 (2 ULiège) From combinatorial games to shape-symmetric morphismsRigo, Michel Scientific conference (2017, November)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 ... [more ▼]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 multidimensional 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. [less ▲]Detailed reference viewed: 52 (4 ULiège) An efficient algorithm to decide periodicity of b-recognisable sets using MSDF conventionBoigelot, Bernard ; Mainz, Isabelle ; Marsault, Victor et alin Leibniz International Proceedings in Informatics (2017, August), 80Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that ... [more ▼]Given an integer base b>1, a set of integers is represented in base b by a language over {0,1,...,b-1}. The set is said to be b-recognisable if its representation is a regular language. It is known that eventually periodic sets are b-recognisable in every base b, and Cobham's theorem implies the converse: no other set is b-recognisable in every base b. We are interested in deciding whether a \$b\$-recognisable set of integers (given as a finite automaton) is eventually periodic. Honkala showed that this problem is decidable in 1986 and recent developments give efficient decision algorithms. However, they only work when the integers are written with the least significant digit first. In this work, we consider the natural order of digits (Most Significant Digit First) and give a quasi-linear algorithm to solve the problem in this case. [less ▲]Detailed reference viewed: 83 (23 ULiège) PrefaceCharlier, Emilie ; Leroy, Julien ; Rigo, Michel in Developments in Language Theory (2017)Detailed reference viewed: 17 (4 ULiège) Des preuves : où, quand, comment ?Rigo, Michel Speech/Talk (2017)Expliquer une démonstration, prouver un résultat, énoncer une conjecture sont des activités qui font partie intégrante du quotidien du mathématicien. Dans ce court exposé, je passerai en revue quelques ... [more ▼]Expliquer une démonstration, prouver un résultat, énoncer une conjecture sont des activités qui font partie intégrante du quotidien du mathématicien. Dans ce court exposé, je passerai en revue quelques exemples de preuves. Certaines sont classiques ou historiques, d'autres sont peut-être moins connues : des preuves à la Ramanujan, des preuves sans mots, le théorème des quatre couleurs, la conjecture de Klepler sur l'empilement de sphères,... Le but est de partager mes réflexions comme chercheur « professionnel » et enseignant. [less ▲]Detailed reference viewed: 82 (6 ULiège) Behavior of digital sequences through exotic numeration systemsLeroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Electronic Journal of Combinatorics (2017), 24(1), 14436Many digital functions studied in the literature, e.g., the summatory function of the base-k sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied ... [more ▼]Many digital functions studied in the literature, e.g., the summatory function of the base-k sum-of-digits function, have a behavior showing some periodic fluctuation. Such functions are usually studied using techniques from analytic number theory or linear algebra. In this paper we develop a method based on exotic numeration systems and we apply it on two examples motivated by the study of generalized Pascal triangles and binomial coefficients of words. [less ▲]Detailed reference viewed: 106 (29 ULiège) Is Büchi's theorem useful for you? (for an audience of logicians)Rigo, Michel Conference (2017, January 17)Almost a century ago, Presburger showed that the first order theory of the natural numbers with addition is decidable. Following the work of B\"uchi in 1960, this result still holds when adding a function ... [more ▼]Almost a century ago, Presburger showed that the first order theory of the natural numbers with addition is decidable. Following the work of B\"uchi in 1960, this result still holds when adding a function \$V_k\$ to the structure, where \$V_k(n)\$ is the largest power of \$k\ge 2\$ diving \$n\$. In particular, this leads to a logical characterization of the \$k\$-automatic sequences. During the last few years, many applications of this result have been considered in combinatorics on words, mostly by J. Shallit and his coauthors. In this talk, we will present this theorem of B\"uchi where decidability relies on finite automata. Then we will review some results about automatic sequences or morphic words that can be proved automatically (i.e., the proof is carried on by an algorithm). Finally, we will sketch the limitation of this technique. With a single line formula, one can prove automatically that the Thue-Morse word has no overlap but, hopefully, not all the combinatorial properties of morphic words can be derived in this way. We will not assume any background in combinatorics on words from the audience. [less ▲]Detailed reference viewed: 38 (4 ULiège) Relations on wordsRigo, Michel in Indagationes Mathematicae (2017), 28In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and ... [more ▼]In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation. In the second part, we mainly focus on abelian equivalence, \$k\$-abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and \$M\$-equivalence. In particular, some new refinements of abelian equivalence are introduced. [less ▲]Detailed reference viewed: 53 (10 ULiège) Counting the number of non-zero coefficients in rows of generalized Pascal trianglesLeroy, Julien ; Rigo, Michel ; Stipulanti, Manon in Discrete Mathematics (2017), 340This paper is about counting the number of distinct (scattered) subwords occurring in a given word. More precisely, we consider the generalization of the Pascal triangle to binomial coefficients of words ... [more ▼]This paper is about counting the number of distinct (scattered) subwords occurring in a given word. More precisely, we consider the generalization of the Pascal triangle to binomial coefficients of words and the sequence (S(n))n≥0 counting the number of positive entries on each row. By introducing a convenient tree structure, we provide a recurrence relation for (S(n))n≥0. This leads to a connection with the 2-regular Stern–Brocot sequence and the sequence of denominators occurring in the Farey tree. Then we extend our construction to the Zeckendorf numeration system based on the Fibonacci sequence. Again our tree structure permits us to obtain recurrence relations for and the F-regularity of the corresponding sequence. [less ▲]Detailed reference viewed: 137 (18 ULiège)