Publications of Michel Rigo
Bookmark and Share    
Full Text
See detailOn Cobham's theorem
Durand, Fabien; Rigo, Michel ULiege

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: 198 (27 ULiège)
Full Text
See detailFrom combinatorial games to shape-symmetric morphisms
Rigo, Michel ULiege

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: 24 (4 ULiège)
Full Text
See detailAn efficient algorithm to decide periodicity of b-recognisable sets using MSDF convention
Boigelot, Bernard ULiege; Mainz, Isabelle ULiege; Marsault, Victor ULiege et al

in Leibniz International Proceedings in Informatics (2017, August), 80

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 ... [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: 27 (6 ULiège)
Full Text
See detailDes preuves : où, quand, comment ?
Rigo, Michel ULiege

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: 48 (2 ULiège)
Full Text
See detailBehavior of digital sequences through exotic numeration systems
Leroy, Julien ULiege; Rigo, Michel ULiege; Stipulanti, Manon ULiege

in Electronic Journal of Combinatorics (2017), 24(1), 14436

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 ... [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: 60 (12 ULiège)
Full Text
See detailIs Büchi's theorem useful for you? (for an audience of logicians)
Rigo, Michel ULiege

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: 25 (2 ULiège)
Full Text
See detailRelations on words
Rigo, Michel ULiege

in Indagationes Mathematicae (2017), 28

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 ... [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: 32 (3 ULiège)
Full Text
See detailCounting the number of non-zero coefficients in rows of generalized Pascal triangles
Leroy, Julien ULiege; Rigo, Michel ULiege; Stipulanti, Manon ULiege

in Discrete Mathematics (2017), 340

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 ... [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: 75 (13 ULiège)
See detailDevelopments in Language Theory
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

Book published by Springer (2017)

The series of international conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and automata. Its scope is very general and includes ... [more ▼]

The series of international conferences on Developments in Language Theory provides a forum for presenting current developments in formal languages and automata. Its scope is very general and includes, among others, the following topics and areas: combinatorial and algebraic properties of words and languages; grammars, acceptors and transducers for strings, trees, graphs, arrays; algebraic theories for automata and languages; codes; efficient text algorithms; symbolic dynamics; decision problems; relationships to complexity theory and logic; picture description and analysis; polyominoes and bidimensional patterns; cryptography; concurrency; cellular automata; bio-inspired computing; quantum computing. The papers submitted to DLT 2017 were from 19 countries including Belgium, Canada, Czech Republic, France, Germany, Hungary, India, Italy, Japan, The Netherlands, Poland, Portugal, Republic of Korea, Russia, Slovakia, South Africa, Thailand and USA. [less ▲]

Detailed reference viewed: 17 (1 ULiège)
Full Text
See detailDeciding game invariance
Duchêne, Eric; Parreau, Aline; Rigo, Michel ULiege

in Information & Computation (2017), 253

In a preivous paper, Duchêne and Rigo introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence S ... [more ▼]

In a preivous paper, Duchêne and Rigo introduced the notion of invariance for take-away games on heaps. Roughly speaking, these are games whose rulesets do not depend on the position. Given a sequence S of positive tuples of integers, the question of whether there exists an invariant game having S as set of P -positions is relevant. In particular, it was recently proved by Larsson et al. that if S is a pair of complementary Beatty sequences, then the answer to this question is always positive. In this paper, we show that for a fairly large set of sequences (expressed by infinite words), the answer to this question is decidable. [less ▲]

Detailed reference viewed: 13 (0 ULiège)
Full Text
See detailCoefficients binomiaux de mots
Rigo, Michel ULiege

Scientific conference (2016, September 15)

Le coefficient binomial (u,v) de deux mots u et v est défini comme le nombre de fois que v apparaît comme sous-suite du mot u. Par exemple, (abbab,ab)=4. Il étend de manière naturelle le coefficient ... [more ▼]

Le coefficient binomial (u,v) de deux mots u et v est défini comme le nombre de fois que v apparaît comme sous-suite du mot u. Par exemple, (abbab,ab)=4. Il étend de manière naturelle le coefficient binomial de deux entiers. Ce concept a été largement étudié depuis plus d'une trentaine d'années (cf. par exemple, Simon et Sakarovitch). Dans cet exposé, je passerai tout d'abord en revue quelques résultats combinatoires classiques pour ensuite m'attarder sur l'équivalence k-binomiale. A l'instar de l'équivalence k-abélienne étudiée par Karhumäki et al., deux mots x et y sont k-binomialement équivalents si leurs coefficients binomiaux (x,v) et (y,v) coïncident pour les mots v de longueur au plus k. En fin d'exposé, j'évoquerai l'extension récente des triangles de Pascal et de Sierpinski à ces coefficients. [less ▲]

Detailed reference viewed: 32 (4 ULiège)
Full Text
See detailDobble, analyse d'un jeu de cartes
Rigo, Michel ULiege

Conference given outside the academic context (2016)

Detailed reference viewed: 76 (1 ULiège)
Full Text
See detailAsymptotic properties of free monoid morphisms
Charlier, Emilie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Linear Algebra & its Applications (2016), 500

Detailed reference viewed: 27 (10 ULiège)
Full Text
See detailDix ans de ``Maths à Modeler à Liège'' ou comment un enseignant/chercheur s'invite dans des classes du secondaire
Rigo, Michel ULiege

Conference given outside the academic context (2016)

Les missions d'un professeur d'université sont multiples : recherche, enseignement mais aussi citoyenneté. Depuis une dizaine d'années, je réalise de multiples activités de sensibilisation aux ... [more ▼]

Les missions d'un professeur d'université sont multiples : recherche, enseignement mais aussi citoyenneté. Depuis une dizaine d'années, je réalise de multiples activités de sensibilisation aux mathématiques : exposés, activités ludiques en petits groupes, etc. En répondant modestement à la question : "les maths ça sert à quoi ?", le but recherché est de démontrer l'utilité souvent méconnue des mathématiques, et de la recherche dans ce domaine (Google, réseaux sociaux, jeux vidéos, magie, etc.). Dans cette présentation, je dresserai tout d'abord l'historique du projet et tenterai d'analyser les actions menées. Ensuite, l'auditoire assistera à un tour de mathémagie et participera, de façon interactive, à un jeu démontrant l'importance du concept de preuve en mathématique. Ces jeux sont tirés de "Situations-Recherche pour la classe" développées par des chercheurs grenoblois. Enfin, j'expliquerai comment des étudiants de l'ULg (bacheliers, masters, étudiants à l'agrégation) et des doctorants participent à cette action. [less ▲]

Detailed reference viewed: 35 (2 ULiège)
Full Text
See detailAdvanced graph theory and combinatorics
Rigo, Michel ULiege

Book published by ISTE-John Wiley & Sons (2016)

This book focuses on some of the main notions arising in graph theory, with an emphasis throughout on the possible applications of the theory and the fruitful links that exist with linear algebra ... [more ▼]

This book focuses on some of the main notions arising in graph theory, with an emphasis throughout on the possible applications of the theory and the fruitful links that exist with linear algebra. Commencing with basic notions such as connectedness, Eulerian, Hamiltonian and planar graphs, opens the way for a variety of applications. A short chapter is devoted to complexity theory, and after a presentation of the chromatic polynomial and Ramsey numbers, the book highlights the important interplay between graph theory and linear algebra. Perron-Frobenius theory is then presented. With rational generating functions and powers of the adjacency matrix, counting walks in a directed multigraph is a recurrent topic of the book and is studied in great detail. Google’s PageRank is then covered in the final chapter of the book. Every application of the theory is accompanied by fully worked examples and proofs, and supplemented by over 100 exercises throughout the book. This allows the student to gain a full and thorough understanding of advanced graph theory and its potential applications. [less ▲]

Detailed reference viewed: 77 (1 ULiège)
Full Text
See detailJouer avec les mots, pourquoi et comment ?
Rigo, Michel ULiege

Learning material (2016)

Ce texte reprend l'essentiel de ma présentation à la Brussels Math. Summer School du 4 août 2015. Il s'agit d'une courte introduction à la combinatoire des mots. A l'instar de Raymond Queneau et ses cent ... [more ▼]

Ce texte reprend l'essentiel de ma présentation à la Brussels Math. Summer School du 4 août 2015. Il s'agit d'une courte introduction à la combinatoire des mots. A l'instar de Raymond Queneau et ses cent mille milliards de poèmes, nous construisons des suites aux propriétés surprenantes. Pour ne pas allonger le texte, nous avons décidé d'éviter l'emploi d'automates finis. Les premiers résultats en combinatoire des mots remontent au début du siècle précédent, avec les travaux du mathématicien norvégien Axel Thue. Cette branche des mathématiques étudie la structure et les arrangements apparaissant au sein de suites finies, ou infinies, de symboles appartenant à un ensemble fini. Un carré est la juxtaposition de deux répétitions d'un même mot. On dira qu'un mot comme `taratata' contient un carré. Il est aisé de vérifier que, si on dispose uniquement de deux symboles, alors tout mot de longueur au moins 4 contient un carré. Cette observation amène de nombreuses questions simples à formuler : Avec trois symboles, peut-on construire un mot arbitrairement long ne contenant pas de carré ? Si on se limite à deux symboles, peut-on construire un mot arbitrairement long sans cube, i.e., évitant la juxtaposition de trois répétitions d'un même mot ? En fonction de la taille de l'alphabet, quels motifs doivent nécessairement apparaître et quels sont ceux qui sont évitables ? Que se passe-t-il si on autorise certaines permutations ? [less ▲]

Detailed reference viewed: 92 (3 ULiège)
Full Text
See detailGeneralized Pascal triangle for binomial coefficients of words
Leroy, Julien ULiege; Rigo, Michel ULiege; Stipulanti, Manon ULiege

in Advances in Applied Mathematics (2016), 80

We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word ... [more ▼]

We introduce a generalization of Pascal triangle based on binomial coefficients of finite words. These coefficients count the number of times a word appears as a subsequence of another finite word. Similarly to the Sierpiński gasket that can be built as the limit set, for the Hausdorff distance, of a convergent sequence of normalized compact blocks extracted from Pascal triangle modulo 2, we describe and study the first properties of the subset of [0, 1] × [0, 1] associated with this extended Pascal triangle modulo a prime p. [less ▲]

Detailed reference viewed: 168 (62 ULiège)
See detailCombinatorics, Words and Symbolic Dynamics
Berthé, Valérie; Rigo, Michel ULiege

Book published by Cambridge University Press (2016)

Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear ... [more ▼]

Internationally recognised researchers look at developing trends in combinatorics with applications in the study of words and in symbolic dynamics. They explain the important concepts, providing a clear exposition of some recent results, and emphasise the emerging connections between these different fields. Topics include combinatorics on words, pattern avoidance, graph theory, tilings and theory of computation, multidimensional subshifts, discrete dynamical systems, ergodic theory, numeration systems, dynamical arithmetics, automata theory and synchronised words, analytic combinatorics, continued fractions and probabilistic models. Each topic is presented in a way that links it to the main themes, but then they are also extended to repetitions in words, similarity relations, cellular automata, friezes and Dynkin diagrams. The book will appeal to graduate students, research mathematicians and computer scientists working in combinatorics, theory of computation, number theory, symbolic dynamics, tilings and stringology. It will also interest biologists using text algorithms. [less ▲]

Detailed reference viewed: 51 (3 ULiège)
Full Text
See detailNon-homogeneous Beatty sequences leading to invariant games
Cassaigne, Julien; Duchêne, Eric; Rigo, Michel ULiege

in SIAM Journal on Discrete Mathematics (2016), 30

We characterize pairs of complementary non-homogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game ... [more ▼]

We characterize pairs of complementary non-homogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game having $\{(A_n,B_n),(B_n,A_n)\mid n> 0\}\cup\{(0,0)\}$ as set of $P$-positions. Using the notion of Sturmian word arising in combinatorics on words, this characterization can be translated into a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. This work partially answers to a question of Larsson et al. raised in Larsson et al. [less ▲]

Detailed reference viewed: 19 (1 ULiège)
Full Text
See detailDefining multiplication in some additive expansions of polynomial rings
Point, Françoise; Rigo, Michel ULiege; Waxweiler, Laurent

in Communications in Algebra (2016), 44

Adapting a result of R. Villemaire on expansions of Presburger arithmetic, we show how to define multiplication in some expansions of the additive reduct of certain Euclidean rings. In particular, this ... [more ▼]

Adapting a result of R. Villemaire on expansions of Presburger arithmetic, we show how to define multiplication in some expansions of the additive reduct of certain Euclidean rings. In particular, this applies to polynomial rings over a finite field. [less ▲]

Detailed reference viewed: 30 (7 ULiège)