References of "Rigo, Michel"
     in
Bookmark and Share    
Full Text
Peer Reviewed
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: 311 (44 ULiège)
Full Text
See detailMathematical models and lockdown
Rigo, Michel ULiege

Speech/Talk (2021)

During the first lockdown due to the health crisis caused by the SARS-CoV-2 better known as Coronavirus, the virus responsible for COVID-19, I wanted to understand the models used by virologists and ... [more ▼]

During the first lockdown due to the health crisis caused by the SARS-CoV-2 better known as Coronavirus, the virus responsible for COVID-19, I wanted to understand the models used by virologists and epidemiologists around the world. In this talk designed for a general audience, I am going to explain these curves that we find all day long in the media and that we want to "flatten". Although I am used to popularizing mathematics, I am not a specialist in applied mathematics, data science nor modeling. So this talk requires a priori very little mathematical knowledge: a bit of common sense and the manipulation of proportions. [less ▲]

Detailed reference viewed: 33 (1 ULiège)
Full Text
See detailAutomatic sequences: from rational bases to trees
Rigo, Michel ULiege; Stipulanti, Manon ULiege

E-print/Working paper (2021)

The nth term of an automatic sequence is the output of a deterministic finite automaton fed with the representation of n in a suitable numeration system. In this paper, instead of considering automatic ... [more ▼]

The nth term of an automatic sequence is the output of a deterministic finite automaton fed with the representation of n in a suitable numeration system. In this paper, instead of considering automatic sequences built on a numeration system with a regular numeration language, we consider these built on languages associated with trees having periodic labeled signatures and, in particular, rational base numeration systems. We obtain two main characterizations of these sequences. The first one is concerned with r-block substitutions where r morphisms are applied periodically. In particular, we provide examples of such sequences that are not morphic. The second characterization involves the factors, or subtrees of finite height, of the tree associated with the numeration system and decorated by the terms of the sequence. [less ▲]

Detailed reference viewed: 32 (2 ULiège)
Full Text
Peer Reviewed
See detailTaking-and-merging games as rewrite games
Duchêne, Eric; Marsault, Victor; Parreau, Aline et al

in Discrete Mathematics and Theoretical Computer Science (2020), 22(4),

This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules{u_i→v_i}: a move consists in the ... [more ▼]

This work is a contribution to the study of rewrite games. Positions are finite words, and the possible moves are defined by a finite number of local rewriting rules{u_i→v_i}: a move consists in the substitution of one occurrence of u_i by v_i, for some i. We introduce and investigate taking-and-merging games, that is, where each rule is of the form a^k→ε. We give sufficient conditions for a game to be such that the losing positions (resp. the positions with a given Grundy value) form a regular language or a context-free language. We formulate several related open questions in parallel with the famous conjecture of Guy about the periodicity of the Grundy function of octal games.Finally we show that more general rewrite games quickly leadt o undecidable problems. Namely, it is undecidable whether there exists a winning position in a given regular language, even if we restrict to games where each move strictly reduces the length of the current position [less ▲]

Detailed reference viewed: 30 (4 ULiège)
Full Text
See detailBinomial^3 : coefficients, equivalence, complexity…
Rigo, Michel ULiege

Scientific conference (2020, July 13)

The binomial coefficient (x,y) of the words x and y is the number of times y appears as a (scattered) subword of x. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices ... [more ▼]

The binomial coefficient (x,y) of the words x and y is the number of times y appears as a (scattered) subword of x. This concept has received a lot of attention, e.g., Simon's congruence, Parikh matrices, reconstruction problem, ... A few years ago, we introduced the k-binomial equivalence: Two words u and v are k-binomially equivalent if the binomial coefficients (u,x) and (v,x) agree for all words x of length up to k. This is a refinement of the usual abelian equivalence. First, I will review several results (joint work with P. Salimov, M. Lejeune, J. Leroy, M. Rosenfeld) related to k-binomial complexity (where factors of length n are counted up to k-binomial equivalence) for Sturmian words, Thue-Morse word and Tribonacci word. Then I will concentrate on k-binomial equivalence classes for finite words. In particular, I will discuss the fact that the submonoid generated by the generators of the free nil-2 group on m generators is isomorphic to the quotient of the free monoid {1,...,m}^∗ by the 2-binomial equivalence (joint work with M. Lejeune, M. Rosenfeld). [less ▲]

Detailed reference viewed: 39 (2 ULiège)
Full Text
See detailModèles mathématiques et confinement, une introduction
Rigo, Michel ULiege

Scientific conference (2020, May 09)

En période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2, le virus responsable du COVID-19, les modèles utilisés par les épidémiologistes du monde entier font l'actualité. Le but de ... [more ▼]

En période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2, le virus responsable du COVID-19, les modèles utilisés par les épidémiologistes du monde entier font l'actualité. Le but de cet exposé à caractère généraliste est d'introduire le modèle simplifié SIR, d'expliquer ces courbes que l'on trouve à longueur de journée dans les média et que l'on souhaite "aplatir" et enfin, de comprendre les limitations inhérentes à la modélisation. Ceci ne nécessite a priori que très peu de connaissances mathématiques : un peu de bon sens et la manipulation des proportions. [less ▲]

Detailed reference viewed: 82 (6 ULiège)
Full Text
See detailModèles mathématiques et confinement
Rigo, Michel ULiege

E-print/Working paper (2020)

En cette période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2 mieux connu comme Coronavirus, le virus responsable du COVID-19, je voulais comprendre les modèles utilisés par les ... [more ▼]

En cette période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2 mieux connu comme Coronavirus, le virus responsable du COVID-19, je voulais comprendre les modèles utilisés par les virologues et épidémiologistes du monde entier. Par la même occasion, je m'en vais vous expliquer ces courbes que l'on trouve à longueur de journée dans les média et que l'on souhaite "aplatir". Habitué à la vulgarisation mathématique, je ne suis pourtant pas un spécialiste des mathématiques appliquées et de la modélisation. Il ne nécessite a priori que très peu de connaissances mathématiques : un peu de bon sens et la manipulation des proportions. Il devrait être accessible dès la 4e année de l'enseignement secondaire. [less ▲]

Detailed reference viewed: 3845 (62 ULiège)
Full Text
See detailLes couleurs des maths
Rigo, Michel ULiege

Speech/Talk (2020)

Les livres de coloriage font fureur à l'école maternelle ! Cependant cette activité “récréative”, lorsqu’on l’applique à des structures mathématiques comme les graphes, révèle des applications bien ... [more ▼]

Les livres de coloriage font fureur à l'école maternelle ! Cependant cette activité “récréative”, lorsqu’on l’applique à des structures mathématiques comme les graphes, révèle des applications bien réelles : création d’horaires compatibles, allocation de ressources, planification, etc. Quand on creuse un peu, on trouve aussi des applications inattendues comme le partage de secrets entre plusieurs intervenants. Vous l’aurez compris, les coloriages des mathématiciens sont parfois difficiles (même pour un ordinateur), toujours surprenants et souvent utiles ! [less ▲]

Detailed reference viewed: 127 (4 ULiège)
Full Text
Peer Reviewed
See detailReconstructing Words from Right-Bounded-Block Words
Fleischmann, Pamela; Lejeune, Marie ULiege; Manea, Florin et al

in Jonoska, N.; Savchuk, D. (Eds.) Developments in Language Theory (2020)

A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a ... [more ▼]

A reconstruction problem of words from scattered factors asks for the minimal information, like multisets of scattered factors of a given length or the number of occurrences of scattered factors from a given set, necessary to uniquely determine a word. We show that a word $w\in\{a,b\}^*$ can be reconstructed from the number of occurrences of at most $min(|w|_a,|w|_b)+1$ scattered factors of the form $a^ib$, where $|w|_a$ is the number of occurrences of the letter $a$ in $w$. Moreover, we generalize the result to alphabets of the form $\{1,…,q\}$ by showing that at most $\sum_{i=1}^{q−1}|w|_i(q−i+1)$ scattered factors suffices to reconstruct $w$. Both results improve on the upper bounds known so far. Complexity time bounds on reconstruction algorithms are also considered here. [less ▲]

Detailed reference viewed: 23 (2 ULiège)
Full Text
See detailFrom combinatorial games to shape-symmetric morphisms
Rigo, Michel ULiege

in Akiyama, Shigeki; Arnoux, Pierre (Eds.) Tiling Dynamical Systems: Introduction to Self-inducing Structures (2020)

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: 64 (17 ULiège)
Full Text
Peer Reviewed
See detailThe carry propagation of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel ULiege et al

in Advances in Applied Mathematics (2020), 120

Given any numeration system, we call carry propagation at a number N the number of digits that are changed when going from the representation of N to the one of N+1, and amortized carry propagation the ... [more ▼]

Given any numeration system, we call carry propagation at a number N the number of digits that are changed when going from the representation of N to the one of N+1, and amortized carry propagation the limit of the mean of the carry propagations at the first N integers, when N tends to infinity, if this limit exists.In the case of the usual base p numeration system, it can be shown that the limit indeed exists and is equal to p/(p −1). We recover a similar value for those numeration systems we consider and for which the limit exists.We address the problem of the existence of the amortized carry propagation in non-standard numeration systems of various kinds: abstract numeration systems, rational base numeration systems, greedy numeration systems and beta-numeration. We tackle the problem with three different types of techniques: combinatorial, algebraic, and ergodic. Fo r each kind of numeration systems that we consider, the relevant method allows for establishing sufficient conditions for the existence of the carry propagation and examples show that these conditions are close to being necessary conditions. [less ▲]

Detailed reference viewed: 33 (7 ULiège)
Full Text
Peer Reviewed
See detailComputing the k-binomial complexity of the Thue–Morse word
Lejeune, Marie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Journal of Combinatorial Theory. Series A (2020), 176

Two words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both the abelian equivalence and ... [more ▼]

Two words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both the abelian equivalence and the Simon congruence. The k-binomial complexity of an infinite word x maps the integer n to the number of classes in the quotient, by this k-binomial equivalence relation, of the set of factors of length n occurring in x. This complexity measure has not been investigation very much. In this paper, we characterize the k-binomial complexity of the Thue–Morse word. The result is striking, compared to more familiar complexity functions. Although the Thue–Morse word is aperiodic, its k-binomial complexity eventually takes only two values. In this paper, we first express the number of occurrences of subwords appearing in iterates of the form Ψ^l(w) for an arbitrary morphism Ψ. We also thoroughly describe the factors of the Thue–Morse word by introducing a relevant new equivalence relation. [less ▲]

Detailed reference viewed: 63 (15 ULiège)
Full Text
Peer Reviewed
See detailOn the binomial equivalence classes of finite words
Lejeune, Marie ULiege; Rigo, Michel ULiege; Rosenfeld, Matthieu

in International Journal of Algebra and Computation (2020)

Two finite words u and v are k-binomially equivalent if, for each word x of length at most k, x appears the same number of times as a subsequence (i.e., as a scattered subword) of both u and v. This ... [more ▼]

Two finite words u and v are k-binomially equivalent if, for each word x of length at most k, x appears the same number of times as a subsequence (i.e., as a scattered subword) of both u and v. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the k-binomial equivalence. We provide an algorithm generating the 2-binomial equivalence class of a word. For k ≥ 2 and alphabet of 3 or more symbols, the language made of lexicographically least elements of every k-binomial equivalence class and the language of singletons, i.e., the words whose k-binomial equivalence class is restricted to a single element, are shown to be non context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-2 group (also called free nilpotent group of class 2) on m generators is isomorphic to the quotient of the free monoid {1, . . . , m}^∗ by the 2-binomial equivalence. [less ▲]

Detailed reference viewed: 34 (5 ULiège)
Full Text
Peer Reviewed
See detailModèles mathématiques et confinement
Rigo, Michel ULiege

in Losanges (2020), 49

En cette période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2 mieux connu comme Coronavirus, le virus responsable du COVID-19, je voulais comprendre les modèles utilisés par les ... [more ▼]

En cette période de confinement dû à la crise sanitaire provoquée par le SARS-CoV-2 mieux connu comme Coronavirus, le virus responsable du COVID-19, je voulais comprendre les modèles utilisés par les virologues et épidémiologistes du monde entier. Par la même occasion, je m’en vais vous expliquer ces courbes que l’on trouve à longueur de journée dans les médias et que l’on souhaite « aplatir ». Habitué à la vulgarisation mathématique, je ne suis pourtant pas un spécialiste des mathématiques appliquées et de la modélisation. Cet article est largement inspiré de The SIR Model for Spread of Disease par Smith et Moore. Il ne nécessite a priori que très peu de connaissances mathématiques : un peu de bon sens et la manipulation des proportions. [less ▲]

Detailed reference viewed: 24 (2 ULiège)
Full Text
Peer Reviewed
See detailTemplates for the k-binomial complexity of the Tribonacci word
Lejeune, Marie ULiege; Rigo, Michel ULiege; Rosenfeld, Matthieu ULiege

in Advances in Applied Mathematics (2020), 112

Consider 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 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≥2, 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. © 2019 Elsevier Inc. [less ▲]

Detailed reference viewed: 37 (6 ULiège)
Full Text
Peer Reviewed
See detailTemplates for the k-binomial complexity of the Tribonacci word
Lejeune, Marie ULiege; Rigo, Michel ULiege; Rosenfeld, Matthieu ULiege

in Lecture Notes in Computer Science (2019, September), 11682

Consider 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 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 𝐱 maps the integer n to the number of pairwise non-equivalent factors of length n occurring in 𝐱. In this paper based on the notion of template introduced by Currie et al., we show that, for all 𝑘≥2, the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity 𝑝(𝑛)=2𝑛+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: 47 (14 ULiège)
Full Text
See detailTemplates for the k-binomial complexity of the Tribonacci word
Lejeune, Marie ULiege; Rigo, Michel ULiege; Rosenfeld, Matthieu ULiege

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: 82 (17 ULiège)
Full Text
Peer Reviewed
See detailComputing the k-binomial complextiy of the Thue-Morse word
Lejeune, Marie ULiege; Leroy, Julien ULiege; Rigo, Michel ULiege

in Lecture Notes in Computer Science (2019), 11647

Two finite words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both abelian equivalence ... [more ▼]

Two finite words are k-binomially equivalent whenever they share the same subwords, i.e., subsequences, of length at most k with the same multiplicities. This is a refinement of both abelian equivalence and the Simon congruence. The k-binomial complexity of an infinite word 𝐱 maps the integer n to the number of classes in the quotient, by this k-binomial equivalence relation, of the set of factors of length n occurring in 𝐱. This complexity measure has not been investigated very much. In this paper, we characterize the k-binomial complexity of the Thue–Morse word. The result is striking, compared to more familiar complexity functions. Although the Thue–Morse word is aperiodic, its k-binomial complexity eventually takes only two values. In this paper, we first express the number of occurrences of subwords appearing in iterates of the form 𝛹^ℓ(𝑤) for an arbitrary morphism 𝛹. We also thoroughly describe the factors of the Thue–Morse word by introducing a relevant new equivalence relation. [less ▲]

Detailed reference viewed: 37 (13 ULiège)
Full Text
Peer Reviewed
See detailAutomatic sequences based on Parry or Bertrand numeration systems
Massuir, Adeline ULiege; Peltomäki, Jarkko; Rigo, Michel ULiege

in Advances in Applied Mathematics (2019), 108

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 ... [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: 57 (15 ULiège)
Full Text
See detailCombinatoire des mots : résultats classiques et avancées récentes
Rigo, Michel ULiege

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: 61 (5 ULiège)