Publications of Michel Rigo
Bookmark and Share    
Full Text
See detailSyntactic complexity of ultimately periodic sets of integers
Rigo, Michel ULiege; Vandomme, Elise ULiege

in Lecture Notes in Computer Science (2011), 6638

We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼]

We compute the cardinality of the syntactic monoid of the language 0^∗rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to some well studied problem: decide whether or not a b-recognizable sets of integers is ultimately periodic. [less ▲]

Detailed reference viewed: 114 (30 ULiège)
Full Text
See detailArithmétique, Automates et Géométrie discrète
Allouche, Jean-Paul; Rigo, Michel ULiege

Diverse speeche and writing (2011)

cours au Collège Belgique

Detailed reference viewed: 83 (10 ULiège)
Full Text
See detailDefining multiplication for polynomials over a finite field.
Rigo, Michel ULiege; Waxweiler, Laurent

E-print/Working paper (2011)

Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is ... [more ▼]

Let $P$ and $Q$ be two non-zero multiplicatively independent polynomials with coefficients in a finite field $\mathbb{F}$. Adapting a result of R.~Villemaire, we show that multiplication of polynomials is a ternary relation $\{(A,B,C)\in\mathbb{F}[X]\mid A.B=C\}$ definable by a first-order formula in a suitable structure containing both functions $V_P$ and $V_Q$ where $V_A(B)$ is defined as the greatest power of $A$ dividing $B$. Such a result has to be considered in the context of a possible analogue of Cobham's theorem for sets of polynomials whose $P$-expansions are recognized by some finite automaton. [less ▲]

Detailed reference viewed: 120 (10 ULiège)
Full Text
See detailThe minimal automaton recognizing mN in a linear numeration system
Charlier, Emilie ULiege; Rampersad, Narad ULiege; Rigo, Michel ULiege et al

in Integers: Electronic Journal of Combinatorial Number Theory (2011), 11B(A4), 1-24

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>1 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 156 (37 ULiège)
Full Text
See detailLogical characterization of recognizable sets of polynomials over a finite field
Rigo, Michel ULiege; Waxweiler, Laurent

in International Journal of Foundations of Computer Science (2011), 22(7), 1549-1563

The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination ... [more ▼]

The ring of integers and the ring of polynomials over a finite field share a lot of properties. Using a bounded number of polynomial coefficients, any polynomial can be decomposed as a linear combination of powers of a non-constant polynomial P playing the role of the base of the numeration. Having in mind the theorem of Cobham from 1969 about recognizable sets of integers, it is natural to study $P$-recognizable sets of polynomials. Based on the results obtained in the Ph.D. thesis of the second author, we study the logical characterization of such sets and related properties like decidability of the corresponding first-order theory. [less ▲]

Detailed reference viewed: 130 (19 ULiège)
Full Text
See detailRepresenting real numbers in a generalized numeration system
Charlier, Emilie ULiege; Le Gonidec, Marion; Rigo, Michel ULiege

in Journal of Computer & System Sciences (2011), 77

We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers ... [more ▼]

We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. [less ▲]

Detailed reference viewed: 107 (23 ULiège)
Full Text
See detailStructure of the minimal automaton of a numeration language
Charlier, Emilie ULiege; Rampersad, Narad ULiege; Rigo, Michel ULiege et al

in Actes de LaCIM 2010 (2010, August)

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. [less ▲]

Detailed reference viewed: 126 (20 ULiège)
Full Text
See detailState complexity of testing divisibility
Charlier, Emilie ULiege; Rampersad, Narad ULiege; Rigo, Michel ULiege et al

in McQuillan, Ian, Pighizzini, Giovanni (Ed.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (2010, August)

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an ... [more ▼]

Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 93 (19 ULiège)
Full Text
See detailInvariant games
Duchêne, Eric; Rigo, Michel ULiege

in Theoretical Computer Science (2010), 411

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: 87 (30 ULiège)
Full Text
See detailSystèmes de numération abstraits et combinatoire des mots (habilitation à diriger des recherches)
Rigo, Michel ULiege

Post doctoral thesis (2010)

We summary the main properties of abstract numeration systems and their links to combinatorics on words and combinatorial game theory.

Detailed reference viewed: 188 (37 ULiège)
Full Text
See detailExtensions and restrictions of Wythoff's game preserving its P positions
Duchêne, Eric; Fraenkel, Aviezri; Nowakowski, Richard et al

in Journal of Combinatorial Theory - Series A (2010), 117

We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules give the same set of P positions. On the other hand, we ... [more ▼]

We consider extensions and restrictions of Wythoff's game having exactly the same set of P positions as the original game. No strict subset of rules give the same set of P positions. On the other hand, we characterize all moves that can be adjoined while preserving the original set of P positions. Testing if a move belongs to such an extended set of rules is shown to be doable in polynomial time. Many arguments rely on the infinite Fibonacci word, automatic sequences and the corresponding number system. With these tools, we provide new two-dimensional morphisms generating an infinite picture encoding respectively P positions of Wythoff's game and moves that can be adjoined. [less ▲]

Detailed reference viewed: 87 (16 ULiège)
Full Text
See detailNumeration Systems: a Link between Number Theory and Formal Language Theory
Rigo, Michel ULiege

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: 112 (14 ULiège)
Full Text
See detailMathémagie et au-delà
Rigo, Michel ULiege

Learning material (2010)

Nous présentons ici 5 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination et le célèbre tour du ``barman aveugle ... [more ▼]

Nous présentons ici 5 tours de magie ne nécessitant aucune habileté particulière de la part de l'apprenti magicien : des tours de cartes, des tours de divination et le célèbre tour du ``barman aveugle avec des gants de boxe''. Contrairement au magicien qui ne dévoile jamais ses secrets, ici, nous expliquons que ces tours reposent sur diverses propriétés et constructions mathématiques. Ces dernières débouchent sur de véritables questions de recherche actuelle en théorie des graphes ou en combinatoire des mots et même sur de possibles applications en robotique et automatisation ! Il y en aura donc pour tous les goûts... et tous les niveaux (suivant l'auditoire, l'exposé sera adapté au niveau des élèves de la 4ième à la 6ième secondaire, voire même aux étudiants universitaires). Ce texte présente donc un matériel qui dépassera souvent (et de loin) le ``spectacle''. [less ▲]

Detailed reference viewed: 505 (36 ULiège)
Full Text
See detailAbstract numeration systems (Chapter 3)
Lecomte, Pierre ULiege; Rigo, Michel ULiege

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

Detailed reference viewed: 95 (9 ULiège)
Full Text
See detailStructure of the minimal automaton of a numeration language and applications to state complexity
Charlier, Emilie ULiege; Rampersad, Narad ULiege; Rigo, Michel ULiege et al

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

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼]

We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number . Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲]

Detailed reference viewed: 68 (9 ULiège)
Full Text
See detailMultidimensional generalized automatic sequences and shape-symmetric morphic words
Charlier, Emilie ULiege; Kärki, Tomi; Rigo, Michel ULiege

in Discrete Mathematics (2010), 310

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 numeration system S. In this paper, we consider an ... [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 numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study its relation to the shapesymmetric infinite words introduced by Arnaud Maes. More precisely, for d>1, we show that a multidimensional infinite word x 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: 75 (17 ULiège)
Full Text
See detailSpecial issue dedicated to the twelfth "Journées montoises d'informatique théorique"
Bruyère, Véronique; Rigo, Michel ULiege

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

Detailed reference viewed: 21 (3 ULiège)
Full Text
See detailIntroduction
Berthé, Valérie; Rigo, Michel ULiege

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

Detailed reference viewed: 13 (3 ULiège)
Full Text
See detailPreliminaries (Chapter 1)
Berthé, Valérie; Rigo, Michel ULiege

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

Detailed reference viewed: 12 (2 ULiège)
Full Text
See detailIndex and References
Berthé, Valérie; Rigo, Michel ULiege

in Combinatorics, Automata and Number Theory (2010)

Detailed reference viewed: 16 (1 ULiège)