References of "Rigo, Michel"
     in
Bookmark and Share    
Full Text
See detailIndex and References
Berthé, Valérie; Rigo, Michel ULg

in Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 7 (1 ULg)
Full Text
See detailAbstract numeration systems (Chapter 3)
Lecomte, Pierre ULg; Rigo, Michel ULg

in Berthé, Valérie; Rigo, Michel (Eds.) Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 75 (9 ULg)
Full Text
See detailPreliminaries (Chapter 1)
Berthé, Valérie; Rigo, Michel ULg

in Berthé, Valérie; Rigo, Michel (Eds.) Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 10 (2 ULg)
Full Text
See detailIntroduction
Berthé, Valérie; Rigo, Michel ULg

in Rigo, Michel; Berthé, Valérie (Eds.) Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 6 (2 ULg)
Full Text
Peer Reviewed
See detailSpecial issue dedicated to the twelfth "Journées montoises d'informatique théorique"
Bruyère, Véronique; Rigo, Michel ULg

in Theoretical Informatics and Applications. Informatique Théorique et Applications (2010), 44(1), 1-192

Detailed reference viewed: 13 (1 ULg)
Full Text
Peer Reviewed
See detailOn the Periodicity of Morphic Words
Halava, Vesa; Harju, Tero; Kärki, Tomi et al

in Lecture Notes in Computer Science (2010), 6224

Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word hω(a). As a ... [more ▼]

Given a morphism h prolongable on a and an integer p, we present an algorithm that calculates which letters occur infinitely often in congruent positions modulo p in the infinite word hω(a). As a corollary, we show that it is decidable whether a morphic word is ultimately p-periodic. Moreover, using our algorithm we can find the smallest similarity relation such that the morphic word is ultimately relationally p-periodic. The problem of deciding whether an automatic sequence is ultimately weakly R-periodic is also shown to be decidable. [less ▲]

Detailed reference viewed: 51 (11 ULg)
Full Text
See detailNumeration Systems: a Link between Number Theory and Formal Language Theory
Rigo, Michel ULg

in Lecture Notes in Computer Science (2010), 6224

We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give some personal ... [more ▼]

We survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies. We do not attempt to be exhaustive but try instead to give some personal interpretations and some research directions. We discuss the notion of numeration systems, recognizable sets of integers and automatic sequences. We brie y sketch some results about transcendence related to the representation of real numbers. We conclude with some applications to combinatorial game theory and veri cation of in nite-state systems and present a list of open problems. [less ▲]

Detailed reference viewed: 77 (11 ULg)
Full Text
Peer Reviewed
See detailInvariant games
Duchêne, Eric; Rigo, Michel ULg

Conference (2009, September)

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

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 are given by a pair of complementary Beatty sequences related to the irrational quadratic number $\alpha_k = (1; \overline{1, k})$. We also provide a recursive characterization of this set. [less ▲]

Detailed reference viewed: 34 (7 ULg)
Full Text
See detailA characterization of multidimensional S-automatic sequences
Charlier, Emilie ULg; Kärki, Tomi ULg; Rigo, Michel ULg

in Actes des rencontres du CIRM, 1 (2009)

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended ... [more ▼]

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2, we state that a multidimensional infinite word x : N^d → \Sigma over a finite alphabet \Sigma is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲]

Detailed reference viewed: 39 (14 ULg)
Full Text
Peer Reviewed
See detailMultidimensional generalized automatic sequences and shape-symmetric morphic words
Charlier, Emilie ULg; Kärki, Tomi; Rigo, Michel ULg

in Proceedings of AutoMathA (2009)

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this paper, we ... [more ▼]

An infinite word is S-automatic if, for all n ≥ 0, its (n + 1)st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study the relationship with the shape-symmetric infinite words as introduced by Arnaud Maes. Precisely, for d ≥ 2, we show that a multidimensional infinite word x : N^d → Σ over a finite alphabet Σ is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲]

Detailed reference viewed: 16 (2 ULg)
Full Text
Peer Reviewed
See detailOn the Recognizability of Self-Generating Sets
Kärki, Tomi ULg; Lacroix, Anne ULg; Rigo, Michel ULg

in Lecture Notes in Computer Science (2009), 5734

Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of ... [more ▼]

Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_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 f(X)\subseteq X for all f in 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. [less ▲]

Detailed reference viewed: 54 (16 ULg)
Full Text
Peer Reviewed
See detailA Decision Problem for Ultimately Periodic Sets in Non-standard Numeration Systems
Bell, Jason; Charlier, Emilie ULg; Fraenkel, Aviezri et al

in International Journal of Algebra & Computation (2009), 19

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

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 for this problem, 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. [less ▲]

Detailed reference viewed: 66 (27 ULg)
Full Text
Peer Reviewed
See detailSyndeticity and independent substitutions
Durand, Fabien; Rigo, Michel ULg

in Advances in Applied Mathematics (2009), 42

We associate in a canonical way a substitution to any abstract numeration system built on a regular language. In relationship with the growth order of the letters, we de ne the notion of two independent ... [more ▼]

We associate in a canonical way a substitution to any abstract numeration system built on a regular language. In relationship with the growth order of the letters, we de ne the notion of two independent substitutions. Our main result is the following. If a sequence x is generated by two independent substitutions, at least one being of exponential growth, then the factors of x appearing in nitely often in x appear with bounded gaps. As an application, we derive an analogue of Cobham's theorem for two independent substitutions (or abstract numeration systems) one with polynomial growth, the other being exponential. [less ▲]

Detailed reference viewed: 40 (11 ULg)
Full Text
See detailLes codes correcteurs
Rigo, Michel ULg

Learning material (2009)

Qu'on le veuille ou non, nous vivons dans un monde où les informations et les moyens de communication sont omniprésents. Les exemples où se mêlent informatique et télécommunications sont nombreux. Que ce ... [more ▼]

Qu'on le veuille ou non, nous vivons dans un monde où les informations et les moyens de communication sont omniprésents. Les exemples où se mêlent informatique et télécommunications sont nombreux. Que ce soit l'Internet, la musique achetée en ligne ou gravée sur CD, les baladeurs de type iPod et autres appareils portables, les supports mémoire de tout type, la photographie numérique, la présence d'ordinateurs de bord sophistiqués dans nos voitures, etc. Sans code correcteur, le CD (implémentant un code correcteur de type Reed-Solomon) et de nombreux autres produits n'auraient probablement jamais connu le succès ! [less ▲]

Detailed reference viewed: 55 (11 ULg)
Full Text
Peer Reviewed
See detailAbstract numeration systems on bounded languages and multiplication by a constant
Charlier, Emilie ULg; Rigo, Michel ULg; Steiner, Wolfgang

in INTEGERS: Electronic Journal of Combinatorial Number Theory (2008), 8(1-A35), 1-19

A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems ... [more ▼]

A set of integers is $S$-recognizable in an abstract numeration system $S$ if the language made up of the representations of its elements is accepted by a finite automaton. For abstract numeration systems built over bounded languages with at least three letters, we show that multiplication by an integer $\lambda\ge2$ does not preserve $S$-recognizability, meaning that there always exists a $S$-recognizable set $X$ such that $\lambda X$ is not $S$-recognizable. The main tool is a bijection between the representation of an integer over a bounded language and its decomposition as a sum of binomial coefficients with certain properties, the so-called combinatorial numeration system. [less ▲]

Detailed reference viewed: 39 (7 ULg)
Full Text
Peer Reviewed
See detailA decision problem for ultimately periodic sets in non-standard numeration systems
Charlier, Emilie ULg; Rigo, Michel ULg

in Actes des Journées Montoises d'Informatique Théorique (2008)

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

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

Detailed reference viewed: 23 (2 ULg)
Full Text
Peer Reviewed
See detailCombinatorics, Automata and Number Theory 2006
Berthé, Valérie; Lecomte, Pierre ULg; Rigo, Michel ULg

in Theoretical Computer Science (2008), 391

Detailed reference viewed: 17 (4 ULg)
Full Text
Peer Reviewed
See detailCubic Pisot Unit Combinatorial Games
Duchêne, Eric; Rigo, Michel ULg

in Monatshefte für Mathematik (2008), 155

Generalized Tribonacci morphisms are de ned on a three letters alphabet and generate the so-called generalized Tribonacci words. We present a family of combinatorial removal games on three piles of tokens ... [more ▼]

Generalized Tribonacci morphisms are de ned on a three letters alphabet and generate the so-called generalized Tribonacci words. We present a family of combinatorial removal games on three piles of tokens whose set of P-positions is coded exactly by these generalized Tribonacci words. To obtain this result, we study combinatorial properties of these words like gaps between consecutive identical letters or recursive de nitions of these words. Beta-numeration systems are then used to show that these games are tractable, i.e., deciding whether a position is a P-position can be checked in polynomial time. [less ▲]

Detailed reference viewed: 25 (2 ULg)
Full Text
Peer Reviewed
See detailA morphic approach to combinatorial games : the Tribonacci case
Duchêne, Eric; Rigo, Michel ULg

in Theoretical Informatics and Applications. Informatique Théorique et Applications (2008), 42

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game ... [more ▼]

We propose a variation of Wythoff's game on three piles of tokens, in the sense that the losing positions can be derived from the Tribonacci word instead of the Fibonacci word for the two piles game. Thanks to the corresponding exotic numeration system built on the Tribonacci sequence, deciding whether a game position is losing or not can be computed in polynomial time. [less ▲]

Detailed reference viewed: 19 (2 ULg)
Full Text
Peer Reviewed
See detailSyntactictal and automatic properties of sets of polynomials over finite fields
Rigo, Michel ULg

in Finite Fields & Their Applications (2008), 42

Syntactical properties of representations of integers in various number systems are well-known and have been extensively studied. In this paper, we transpose the notion of recognizable set of integers ... [more ▼]

Syntactical properties of representations of integers in various number systems are well-known and have been extensively studied. In this paper, we transpose the notion of recognizable set of integers into the framework of the polynomial ring over a finite field F. We define B-recognizable sets of polynomials over F and consider their first properties. [less ▲]

Detailed reference viewed: 17 (2 ULg)