References of "Rigo, Michel"
     in
Bookmark and Share    
Full Text
Peer Reviewed
See detailAn analogue of Cobham's theorem for graph directed iterated function systems
Charlier, Emilie ULg; Leroy, Julien ULg; Rigo, Michel ULg

in Advances in Mathematics (in press)

Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend ... [more ▼]

Feng and Wang showed that two homogeneous iterated function systems in $\mathbb{R}$ with multiplicatively independent contraction ratios necessarily have different attractors. In this paper, we extend this result to graph directed iterated function systems in $\mathbb{R}^n$ with contraction ratios that are of the form $\frac{1}{\beta}$, for integers $\beta$. By using a result of Boigelot {\em et al.}, this allows us to give a proof of a conjecture of Adamczewski and Bell. In doing so, we link the graph directed iterated function systems to Büchi automata. In particular, this link extends to real numbers $\beta$. We introduce a logical formalism that permits to characterize sets of $\mathbb{R}^n$ whose representations in base $\beta$ are recognized by some Büchi automata. This result depends on the algebraic properties of the base: $\beta$ being a Pisot or a Parry number. The main motivation of this work is to draw a general picture representing the different frameworks where an analogue of Cobham's theorem is known. [less ▲]

Detailed reference viewed: 22 (5 ULg)
Full Text
Peer Reviewed
See detailAnother Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words (long version)
Rigo, Michel ULg; Salimov, Pavel

in Theoretical Computer Science (in press)

The binomial coefficient of two words $u$ and $v$ is the number of times $v$ occurs as a subsequence of $u$. Based on this classical notion, we introduce the $m$-binomial equivalence of two words refining ... [more ▼]

The binomial coefficient of two words $u$ and $v$ is the number of times $v$ occurs as a subsequence of $u$. Based on this classical notion, we introduce the $m$-binomial equivalence of two words refining the abelian equivalence. Two words $x$ and $y$ are $m$-binomially equivalent, if, for all words $v$ of length at most $m$, the binomial coefficients of $x$ and $v$ and respectively, $y$ and $v$ are equal. The $m$-binomial complexity of an infinite word $x$ maps an integer $n$ to the number of $m$-binomial equivalence classes of factors of length $n$ occurring in $x$. We study the first properties of $m$-binomial equivalence. We compute the $m$-binomial complexity of two classes of words: Sturmian words and (pure) morphic words that are fixed points of Parikh-constant morphisms like the Thue--Morse word, i.e., images by the morphism of all the letters have the same Parikh vector. We prove that the frequency of each symbol of an infinite recurrent word with bounded $2$-binomial complexity is rational. [less ▲]

Detailed reference viewed: 11 (1 ULg)
Full Text
Peer Reviewed
See detailDefining multiplication in some additive expansions of polynomial rings
Point, Françoise; Rigo, Michel ULg; Waxweiler, Laurent

in Communications in Algebra (in press)

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: 9 (2 ULg)
Full Text
See detailOn Cobham's theorem
Durand, Fabien; Rigo, Michel ULg

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: 118 (21 ULg)
Full Text
See detailInvariant games and non-homogeneous Beatty sequences
Rigo, Michel ULg

Scientific conference (2015, January 08)

The aim of this talk is to introduce some notions arising in combinatorial game theory and make the connection with combinatorics on words. We characterize all pairs of complementary non-homogenous Beatty ... [more ▼]

The aim of this talk is to introduce some notions arising in combinatorial game theory and make the connection with combinatorics on words. We characterize all pairs of complementary non-homogenous Beatty sequences (A_n)n≥0 and (B_n)n≥0 for which there exists an invariant game having exactly {(A_n,B_n)∣n≥0}∪{(B_n,A_n)∣n≥0} as set of P-positions. Using the notion of Sturmian word and tools arising in symbolic dynamics and combinatorics on words, this characterization can be translated to a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. Given any four real numbers defining the two sequences, up to these tests, we can therefore decide whether or not such an invariant game exists. [less ▲]

Detailed reference viewed: 12 (5 ULg)
Full Text
Peer Reviewed
See detailAvoiding 2-binomial squares and cubes
Rao, Michaël; Rigo, Michel ULg; Salimov, Pavel

in Theoretical Computer Science (2015), 572

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 7 (1 ULg)
Full Text
Peer Reviewed
See detailA New Approach to the 2-Regularity of the ℓ-Abelian Complexity of 2-Automatic Sequences
Parreau, Aline; Rigo, Michel ULg; Rowland, Eric ULg et al

in The Electronic Journal of Combinatorics (2015), 22(1), 127

We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem ... [more ▼]

We prove that a sequence satisfying a certain symmetry property is 2-regular in the sense of Allouche and Shallit, i.e., the Z-module generated by its 2-kernel is finitely generated. We apply this theorem to develop a general approach for studying the l-abelian complexity of 2-automatic sequences. In particular, we prove that the period-doubling word and the Thue--Morse word have 2-abelian complexity sequences that are 2-regular. Along the way, we also prove that the 2-block codings of these two words have 1-abelian complexity sequences that are 2-regular. [less ▲]

Detailed reference viewed: 23 (3 ULg)
See detailFormal languages, automata and numeration systems, volume 1: Introduction to combinatorics on words
Rigo, Michel ULg

Book published by ISTE-Wiley (2014)

The goal is not to have an encyclopedic presentation of the subject, but to familiarize the reader with a series of selected selected topics on words (words, morphisms, factor complexity, Sturmian words ... [more ▼]

The goal is not to have an encyclopedic presentation of the subject, but to familiarize the reader with a series of selected selected topics on words (words, morphisms, factor complexity, Sturmian words, ...). The philosophy is to rigorously present the concepts being illustrated with many examples (particularly in relations to numeration systems or symbolic dynamics). The reader should be able to quickly gain access to current research problems or attend a conference on the subject. Interactions between combinatorics, arithmetic and automata theory are also highlighted. The book requires little (or no) prerequisites and thus should be accessible to a wide audience (computer scientists/mathematicians, at Master/graduate level). The first volume can be used for a course in one semester in combinatorics of words (e.g. I give regularly the first two chapters to read to my students, the last one serving as complement for the 'advanced' students). [less ▲]

Detailed reference viewed: 9 (2 ULg)
Full Text
See detailA conjecture on the 2-abelian complexity of the Thue-Morse word
Rigo, Michel ULg; Parreau, Aline ULg; Vandomme, Elise ULg

Scientific conference (2014, January 20)

The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k ... [more ▼]

The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. For example, it is trivially abelian periodic and its abelian complexity takes only two values. For an integer k, the k-abelian complexity is a generalization of the abelian complexity, corresponding to the case where k=1. Formally, two words u and v of the same length are k-abelian equivalent if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The aim of this talk is to study the 2-abelian complexity a(n) of the Thue-Morse word. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a work of Madill and Rampersad (2012) where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will present some arguments supporting our conjecture. They are based on functions counting some subword of length 2 occuring in prefixes of the Thue-Morse word. [less ▲]

Detailed reference viewed: 37 (13 ULg)
Full Text
Peer Reviewed
See detailSpecial issue dedicated to the 14th "Journées montoises d'informatique théorique"
Bruyère, Véronique; Jungers, Raphaël; Hollanders et al

in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2014), 48

Detailed reference viewed: 8 (0 ULg)
Full Text
Peer Reviewed
See detailOn the number of abelian bordered words (with an example of automatic theorem-proving)
Goc, Daniel; Rampersad, Narad; Rigo, Michel ULg et al

in International Journal of Foundations of Computer Science (2014), 8

In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible ... [more ▼]

In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible symmetric Motzkin paths and paths in $\mathbb{Z}$ not returning to the origin. This study can be extended to abelian unbordered words over an arbitrary alphabet and we derive expressions to compute the number of these words. In particular, over a $3$-letter alphabet, the connection with paths in the triangular lattice is made. Finally, we characterize the lengths of the abelian unbordered factors occurring in the Thue--Morse word using some kind of automatic theorem-proving provided by a logical characterization of the $k$-automatic sequences. [less ▲]

Detailed reference viewed: 6 (0 ULg)
See detailFormal languages, automata and numeration systems, volume 2: Applications to recognizability and decidability
Rigo, Michel ULg

Book published by ISTE-Wiley (2014)

The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that ... [more ▼]

The interplay between words, computability, algebra and arithmetic has now proved its relevance and fruitfulness. Indeed, the cross-fertilization between formal logic and finite automata (such as that initiated by J.R. Büchi) or between combinatorics on words and number theory has paved the way to recent dramatic developments, for example, the transcendence results for the real numbers having a “simple” binary expansion, by B. Adamczewski and Y. Bugeaud. This book is at the heart of this interplay through a unified exposition. Objects are considered with a perspective that comes both from theoretical computer science and mathematics. Theoretical computer science offers here topics such as decision problems and recognizability issues, whereas mathematics offers concepts such as discrete dynamical systems. The main goal is to give a quick access, for students and researchers in mathematics or computer science, to actual research topics at the intersection between automata and formal language theory, number theory and combinatorics on words. The second of two volumes on this subject, this book covers regular languages, numeration systems, formal methods applied to decidability issues about infinite words and sets of numbers. [less ▲]

Detailed reference viewed: 15 (0 ULg)
Full Text
Peer Reviewed
See detailA note on abelian returns in rotation words
Rampersad, Narad; Rigo, Michel ULg; Salimov, Pavel ULg

in Theoretical Computer Science (2014), 528

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 ... [more ▼]

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. [less ▲]

Detailed reference viewed: 88 (16 ULg)
Full Text
See detailMathémagie III
Rigo, Michel ULg

Speech/Talk (2013)

Cet exposé est dans la continuité de mes précédentes prestations comme apprenti-magicien. Il s'adresse au plus grand nombre et ne nécessite pas de prérequis particulier. Je réaliserai 6 ou 7 tours de ... [more ▼]

Cet exposé est dans la continuité de mes précédentes prestations comme apprenti-magicien. Il s'adresse au plus grand nombre et ne nécessite pas de prérequis particulier. Je réaliserai 6 ou 7 tours de "mathémagie" (tours de cartes, divination, mentalisme,...). Pour chaque tour, le scénario sera identique : réalisation du tour, explication, mise en évidence des structures et résultats mathématiques sous-jacents et enfin, illustration de ces concepts mathématiques mis en oeuvre dans d'autres contextes (informatique, théorie de l'information, ...) [less ▲]

Detailed reference viewed: 146 (9 ULg)
Full Text
Peer Reviewed
See detailAnother Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
Rigo, Michel ULg; Salimov, Pavel ULg

in Lecture Notes in Computer Science (2013), 8079

The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the ... [more ▼]

The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the abelian equivalence. The m-binomial complexity of an infinite word x maps an integer n to the number of m-binomial equivalence classes of factors of length n occurring in x. We study the first properties of m-binomial equivalence. We compute the m-binomial complexity of the Sturmian words and of the Thue-Morse word. We also mention the possible avoidance of 2-binomial squares. [less ▲]

Detailed reference viewed: 74 (23 ULg)
Full Text
Peer Reviewed
See detailOn the Number of Abelian Bordered Words
Rampersad, Narad; Rigo, Michel ULg; Salimov, Pavel ULg

in Lecture Notes in Computer Science (2013), 7907

In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible ... [more ▼]

In the literature, many bijections between (labeled) Motzkin paths and various other combinatorial objects are studied. We consider abelian (un)bordered words and show the connection with irreducible symmetric Motzkin paths and paths in Z not returning to the origin. This study can be extended to abelian unbordered words over an arbitrary alphabet and we derive expressions to compute the number of these words. In particular, over a 3-letter alphabet, the connection with paths in the triangular lattice is made. Finally, we study the lengths of the abelian unbordered factors occurring in the Thue--Morse word. [less ▲]

Detailed reference viewed: 66 (14 ULg)
Full Text
Peer Reviewed
See detailSome properties of abelian return words
Rigo, Michel ULg; Salimov, Pavel ULg; Vandomme, Elise ULg

in Journal of Integer Sequences (2013), 16

We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in ... [more ▼]

We investigate some properties of abelian return words as recently introduced by S. Puzynina and L. Q. Zamboni. In particular, we obtain a characterization of Sturmian words with non-null intercept in terms of the finiteness of the set of abelian return words to all prefixes. We describe this set of abelian returns for the Fibonacci word but also for the 2-automatic Thue--Morse word. We also investigate the relationship existing between abelian complexity and finiteness of the set of abelian returns to all prefixes. We end this paper by considering the notion of abelian derived sequence. It turns out that, for the Thue--Morse word, the set of abelian derived sequences is infinite. [less ▲]

Detailed reference viewed: 128 (35 ULg)
Full Text
Peer Reviewed
See detailMultidimensional extension of the Morse-Hedlund theorem
Durand, Fabien; Rigo, Michel ULg

in European Journal of Combinatorics (2013), 34

Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of ... [more ▼]

Nivat's conjecture is about the link between the pure periodicity of a subset M of Z^2, i.e., invariance under translation by a fixed vector, and some upper bound on the function counting the number of different rectangular blocks occurring in $M$. Attempts to solve this conjecture have been considered during the last fifteen years. Let d>1. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d definable by a first order formula in the Presburger arithmetic <Z;<,+>. With this latter notion and using a powerful criterion due to Muchnik, we solve an analogue of Nivat's conjecture and characterize sets of Z^d definable in <Z;<,+> in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often. [less ▲]

Detailed reference viewed: 61 (7 ULg)
Full Text
See detail2-abelian complexity of the Thue-Morse sequence
Rigo, Michel ULg; Vandomme, Elise ULg

Scientific conference (2012, December 14)

Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of ... [more ▼]

Let k be an integer. Two words u and v of the same length are k-abelian equivalent, if they have the same prefix (resp. suffix) of length k-1 and if, for all words x of length k, the numbers of occurrences of x in u and v are the same. This notion has received some recent interest, see the works of Karhumäki et al. The k-abelian complexity of an infinite word x maps an integer n to the number of k-abelian classes partitioning the set of factors of length n occurring in x. The Thue-Morse word is a well-known and extensively studied 2-automatic sequence. It is trivially abelian periodic and its (1)-abelian complexity takes only two values. The aim of this talk is to explain how to compute the 2-abelian complexity a(n) of the Thue-Morse word, showing in particular that it is unbounded. We conjecture that a(n) is 2-regular in the sense of Allouche and Shallit. This question can be related to a recent work of Madill and Rampersad where the (1)-abelian complexity of the paper folding word is shown to be 2-regular. We will also explain why the usual logical framework introduced by Büchi and popularized by Bruyère (indeed, automatic sequences can be characterized in an extension of the Presburger arithmetic) and the recent work of Charlier et al. about "automatic theorem-proving" of properties of automatic sequences cannot be applied to these questions related to abelian complexity. [less ▲]

Detailed reference viewed: 141 (40 ULg)