References of "Rigo, Michel"
     in
Bookmark and Share    
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: 83 (18 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: 7 (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: 48 (9 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: 48 (9 ULg)
Full Text
See detailMathémagie III
Rigo, Michel ULg

Speech (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: 74 (8 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: 46 (15 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: 50 (11 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: 96 (23 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: 50 (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: 105 (26 ULg)
Full Text
See detailNumeration systems: a link between number theory and formal language theory
Rigo, Michel ULg

Scientific conference (2012, November 28)

In this talk, we survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies about sets of integers whose base k expansions are recognized by some ... [more ▼]

In this talk, we survey facts mostly emerging from the seminal results of Alan Cobham obtained in the late sixties and early seventies about sets of integers whose base k expansions are recognized by some finite automaton. We do not expect any background from the audience, so we will present the basic definitions and many examples. We will not attempt to be exhaustive but try instead to present some actual research directions about numeration systems, recognizable sets of integers and automatic sequences. If there is enough time, we will briefly sketch some results about transcendence related to the representation of real numbers. [less ▲]

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

Conference (2012, September 11)

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

We investigate some properties of abelian return words as recently introduced by Puzynina and 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: 18 (6 ULg)
Full Text
Peer Reviewed
See detailOn the concrete complexity of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel ULg et al

Conference (2012, September 11)

We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n ... [more ▼]

We consider two kinds of questions about the successor function. The first one is concerned with the estimation of the length of the carry propagation when applying the successor map on the first n integers (or more generally on the first n elements in a given language). This leads to the notion of amortized (or average) carry propagation when applying the successor function. The second question is a computational issue: estimating the number of operations (in classical terms of Turing machines complexity) required to compute the representations of the first n integers from the first one by applying n times the successor function. This leads to the notion of (amortized) complexity, i.e., the average amount of computations required to obtain the successor of an element. [less ▲]

Detailed reference viewed: 37 (3 ULg)
Full Text
See detailLe problème de Prouhet
Rigo, Michel ULg

Conference (2012, August 22)

Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de ... [more ▼]

Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de nombres entiers) mais leurs éventuelles solutions peuvent s'avérer redoutables. Dans cet exposé, on s'intéressera à un problème accessible dû à Prouhet (1851) : "partitionner l'ensemble {0,1,2,...,2^N-1} en deux sous-ensembles A et B de même taille de telle sorte que les sommes des éléments de A et B soient égales, les sommes des carrés des éléments de A et B soient égales, ..., les sommes des puissances (N-1)-ièmes des éléments de A et B soient égales ". Par exemple, pour N=3, on trouve 0+3+5+6=1+2+4+7 et 0^2+3^2+5^2+6^2=1^2+2^2+4^2+7^2. On en présentera une solution reposant de façon élégante sur les écritures en base 2 et on s'autorisera quelques digressions : produit de sinus, répétition et chevauchement, jeu d'échecs, généralisations, pavages colorés, composition musicale, tours de Hanoï, cubes magiques, ... Cet exposé est construit pour être une balade arithmétique amusante et inattendue, pouvant montrer à des élèves ouverts, un peu comme le prétend André DELEDICQ, que les mathématiques peuvent être jubilatoires. [less ▲]

Detailed reference viewed: 52 (10 ULg)
Full Text
See detailAutour des systèmes de numération abstraits
Rigo, Michel ULg

Conference (2012, June 12)

Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on ... [more ▼]

Un système de numération, comme notre système décimal usuel, peut être vu comme une bijection entre l'ensemble des entiers naturels et le langage formé des représentations de ces entiers. Lorsque l'on considère, de façon générale, une numération basée sur une suite strictement croissante d'entiers et pour laquelle les représentations sont obtenues par un algorithme glouton, la bijection qui à un entier associe sa représentation préserve l'ordre naturel. Ainsi, un système de numération abstrait est la donnée d'un langage L infini (le plus souvent régulier) ordonné par ordre généalogique croissant. L'entier n est alors représenté par le n-ième mot du langage L. L'introduction, il y a une dizaine d'années, de ces systèmes abstraits a été motivée par le théorème de Cobham de 1969 qui s'intéresse aux ensembles reconnaissables d'entiers. Un ensemble X d'entiers est dit S-reconnaissable, pour une numération fixée S, si l'ensemble des représentations dans le système S des éléments de X forme un langage régulier. Ainsi les ensembles S-reconnaissables sont, d'un certain point de vue, particulièrement simples puisque décrits par un automate fini. Le théorème de Cobham stipule que les seuls ensembles d'entiers simultanément reconnaissables pour deux bases entières k et l suffisamment indépendantes, à savoir multiplicativement indépendantes, sont exactement les unions finies de progressions arithmétiques. Ce théorème a été le point de départ de nombreux travaux de recherche au cours de ces quarante dernières années (généralisations à des numérations non standards, à plusieurs dimensions, formalisme logique,... ). Dans ce survol liant théorie élémentaire des nombres et théorie des automates, nous nous proposons de présenter quelques questions et développements en lien directe avec cette question générale : existe-t-il un lien entre les propriétés arithmétiques des nombres (e.g., carré parfait, nombre premier, critère de divisibilité, ...) et les propriétés syntaxiques de leurs représentations ? Les propriétés décrites par automates finis sont-elles, par exemple, stables en appliquant des opérations arithmétiques élémentaires comme l'addition ou la multiplication par une constante ? Les automates permettent également de tracer des liens avec la combinatoire des mots (suites automatiques au sens d'Allouche et Shallit et plus généralement mots morphiques engendrés par substitution) ou d'exprimer certains problèmes de décision dont la solution revient à étudier la complexité en nombre d'états (state complexity) de certaines familles de langages. [less ▲]

Detailed reference viewed: 34 (4 ULg)
Full Text
See detailRecognizable sets of integers
Rigo, Michel ULg

Conference (2012, June)

Detailed reference viewed: 34 (1 ULg)
Full Text
See detailMathémagie 2
Rigo, Michel ULg

Speech (2012)

Nous présentons ici des 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 etc. Contrairement au magicien qui ne ... [more ▼]

Nous présentons ici des 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 etc. 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 (décomposition d'une permutation en produit de cycle, suites linéaires récurrentes, ...). Il y en aura donc pour tous les goûts... et tous les niveaux. Dans la mesure du possible, nous présenterons de "nouveaux" tours qui n'auraient pas déjà été dévoilés dans un exposé précédent. [less ▲]

Detailed reference viewed: 92 (9 ULg)
Full Text
Peer Reviewed
See detailLe problème de Prouhet
Rigo, Michel ULg

in Losanges (2012), 19

Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de ... [more ▼]

Si on pense aux nombres, à leur théorie et à l'arithmétique, on fait rapidement face à de nombreuses questions simples à énoncer (elles ne font intervenir que des sommes, des produits ou des puissances de nombres entiers) mais leurs éventuelles solutions peuvent s'avérer redoutables. Dans ce texte relatif à mon intervention du 22 août 2012 au congrès annuel de la SBPMef, on s'intéressera à un problème accessible : partitionner l'ensemble {0,1,2,...,2^{n+1}-1} en deux sous-ensembles A et B de même taille de telle sorte que les sommes des éléments de A et B soient égales, les sommes des carrés des éléments de A et B soient égales, ..., les sommes des puissances n-ièmes des éléments de A et B soient égales. Par exemple, pour n=2, on trouve 0+3+5+6=1+2+4+7 et 0^2+3^2+5^2+6^2=1^2+2^2+4^2+7^2. On en présentera une solution reposant de façon élégante sur les écritures en base $2$ et on s'autorisera quelques digressions : produit de sinus, répétition et chevauchement, jeu d'échecs, composition musicale, ... Ce texte est construit pour être une balade arithmétique amusante et inattendue, pouvant montrer à des élèves ouverts, un peu comme le prétend André Deledicq, que les mathématiques peuvent être jubilatoires. [less ▲]

Detailed reference viewed: 4 (1 ULg)
Full Text
Peer Reviewed
See detailSyntactic complexity of ultimately periodic sets of integers and application to a decision procedure
Lacroix, Anne ULg; Rampersad, Narad; Rigo, Michel ULg et al

in Fundamenta Informaticae (2012), 116

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 a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic. [less ▲]

Detailed reference viewed: 41 (2 ULg)