Michel Rigo

MFCS Conference 2022 Conference Paper

On Extended Boundary Sequences of Morphic and Sturmian Words

• Michel Rigo
• Manon Stipulanti
• Markus A. Whiteland

Generalizing the notion of the boundary sequence introduced by Chen and Wen, the nth term of the 𝓁-boundary sequence of an infinite word is the finite set of pairs (u, v) of prefixes and suffixes of length 𝓁 appearing in factors uyv of length n+𝓁 (n ≥ 𝓁 ≥ 1). Otherwise stated, for increasing values of n, one looks for all pairs of factors of length 𝓁 separated by n-𝓁 symbols. For the large class of addable numeration systems U, we show that if an infinite word is U-automatic, then the same holds for its 𝓁-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and U-automatic words with a boundary sequence that is not U-automatic. In the second part of the paper, we study the 𝓁-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.

I&C Journal 2017 Journal Article

Deciding game invariance

• Eric Duchêne
• Aline Parreau
• Michel Rigo

In a previous 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.

TCS Journal 2015 Journal Article

Avoiding 2-binomial squares and cubes

• Michaël Rao
• Michel Rigo
• Pavel Salimov

Two finite words u, v are 2-binomially equivalent if, for all words x of length at most 2, the number of occurrences of x as a (scattered) subword of u is equal to the number of occurrences of x in v. This notion is a refinement of the usual abelian equivalence. A 2-binomial square is a word uv where u and v are 2-binomially equivalent. In this paper, considering pure morphic words, we prove that 2-binomial squares (resp. cubes) are avoidable over a 3-letter (resp. 2-letter) alphabet. The sizes of the alphabets are optimal.

TCS Journal 2014 Journal Article

A note on abelian returns in rotation words

• Narad Rampersad
• Michel Rigo
• Pavel Salimov

Pursuing the study started by Rigo, Salimov and Vandomme, we use elementary number-theoretic techniques to characterize rotation words having a finite set of abelian returns to all prefixes. We also make the connection between the three gap theorem and the number of semi-abelian returns for Sturmian words, simplifying some arguments developed by Puzynina and Zamboni.

TCS Journal 2010 Journal Article

Invariant games

• Eric Duchêne
• Michel Rigo

In the context of 2-player removal games, we define the notion of invariant game for which each allowed move is independent of the position it is played from. We present a family of invariant games which are variations of Wythoff’s game. The set of P -positions of these games is given by a pair of complementary Beatty sequences related to the irrational quadratic number α k = ( 1; 1, k ¯ ). We also provide a recursive characterization of this set.

MFCS Conference 2009 Conference Paper

On the Recognizability of Self-generating Sets

• Tomi Kärki
• Anne Lacroix
• Michel Rigo

Abstract Let I be a finite set of integers and F be a finite set of maps of the form n ↦ k i n + ℓ i with integer coefficients. For an integer base k ≥ 2, we study the k -recognizability of the minimal set X of integers containing I and satisfying ϕ ( X ) ⊆ X for all ϕ ∈ F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k i are multiplicatively independent, then X is not k -recognizable for any k ≥ 2.

MFCS Conference 2008 Conference Paper

A Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems

• Emilie Charlier
• Michel Rigo

Abstract Consider a non-standard numeration system like the one built over the Fibonacci sequence where nonnegative integers are represented by words over {0, 1} without two consecutive 1. Given a set X of integers such that the language of their greedy representations in this system is accepted by a finite automaton, we consider the problem of deciding whether or not X is a finite union of arithmetic progressions. We obtain a decision procedure under some hypothesis about the considered numeration system. In a second part, we obtain an analogous decision result for a particular class of abstract numeration systems built on an infinite regular language.

TCS Journal 2008 Journal Article

Preface to the special issue dedicated to combinatorics, automata and number theory

• Valérie Berthé
• Pierre Lecomte
• Michel Rigo

MFCS Conference 2005 Conference Paper

Abstract Numeration Systems and Tilings

• Valérie Berthé
• Michel Rigo

Abstract An abstract numeration system is a triple S = ( L, Σ, <) where (Σ, <) is a totally ordered alphabet and L a regular language over Σ; the associated numeration is defined as follows: by enumerating the words of the regular language L over Σ with respect to the induced genealogical ordering, one obtains a one-to-one correspondence between ℕ and L. Furthermore, when the language L is assumed to be exponential, real numbers can also be expanded. The aim of the present paper is to associate with S a self-replicating multiple tiling of ăthe space, under the following assumption: the adjacency matrix of the trimmed minimal automaton recognizing L is primitive with a dominant eigenvalue being a Pisot unit. This construction generalizes the classical constructions performed for Rauzy fractals associated with Pisot substitutions [16], and for central tiles associated with a Pisot beta-numeration [23].

MFCS Conference 2002 Conference Paper

Characterizing Simpler Recognizable Sets of Integers

• Michel Rigo

Abstract For the k -ary numeration system, we characterize the sets of integers such that the corresponding representations make up a star-free regular language. This result can be transposed to some linear numeration systems built upon a Pisot number like the Fibonacci system and also to k -adic numeration systems. Moreover we study the problem of the base dependence of this property and obtain results which are related to Cobham’s Theorem.

TCS Journal 2001 Journal Article

Numeration systems on a regular language: arithmetic operations, recognizability and formal power series

• Michel Rigo

Generalizations of numeration systems in which N is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language L⊂Σ∗. For these systems, we obtain a characterization of recognizable sets of integers in terms of N -rational formal series. After a study of the polynomial regular languages, we show that, if the complexity of L is Θ(nl) (resp. if L is the complement of a polynomial language), then multiplication by λ∈N preserves recognizability only if λ=βl+1 (resp. if λ≠(#Σ)β ) for some β∈N. Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent.

TCS Journal 2000 Journal Article

Generalization of automatic sequences for numeration systems on a regular language

• Michel Rigo

Let L be an infinite regular language on a totally ordered alphabet (Σ, <). Feeding a finite deterministic automaton (with output) with the words of L, enumerated lexicographically with respect to <, leads to an infinite sequence over the output alphabet of the automaton. This process generalizes the concept of k-automatic sequence for abstract numeration systems on a regular language (instead of systems in base k). Here, we study the first properties of these sequences and their relations with numeration systems.