Publications of Michel Rigo
Bookmark and Share    
Full Text
See detailSyntactictal and automatic properties of sets of polynomials over finite fields
Rigo, Michel ULiege

Conference (2006, October)

Detailed reference viewed: 26 (1 ULiège)
Full Text
See detailAbstract numeration systems : a survey.
Rigo, Michel ULiege

Conference (2006, August)

Detailed reference viewed: 39 (4 ULiège)
Full Text
See detailA note on syndeticity, recognizable sets and Cobham's theorem
Rigo, Michel ULiege; Waxweiler, Laurent ULiege

in Bulletin of the European Association for Theoretical Computer Science (2006), 88

In this note, we give an alternative proof of the following result. Let p,q>=2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-recognizable, then it is ... [more ▼]

In this note, we give an alternative proof of the following result. Let p,q>=2 be two multiplicatively independent integers. If an infinite set of integers is both p- and q-recognizable, then it is syndetic. Notice that this result is needed in the classical proof of the celebrated Cobham’s theorem. Therefore the aim of this paper is to complete [13] and [1] to obtain an accessible proof of Cobham’s theorem. [less ▲]

Detailed reference viewed: 26 (2 ULiège)
Full Text
See detailStructural properties of bounded languages with respect to multiplication by a constant
Charlier, Emilie ULiege; Rigo, Michel ULiege

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

We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative ... [more ▼]

We consider the preservation of recognizability of a set of integers after multiplication by a constant for numeration systems built over a bounded language. As a corollary we show that any nonnegative integer can be written as a sum of binomial coefficients with some prescribed properties. [less ▲]

Detailed reference viewed: 28 (1 ULiège)
Full Text
See detailAutomates et systèmes de numération
Rigo, Michel ULiege

in Bulletin de la Société Royale des Sciences de Liège (2005), 73

Ce survol introductif est basé sur une mini-conférence réalisée à la Société Royale des Sciences de Liège en avril 2004 et sur un exposé réalisé à l’IUFM de Reims en juin 2003 (Integrating Technologies ... [more ▼]

Ce survol introductif est basé sur une mini-conférence réalisée à la Société Royale des Sciences de Liège en avril 2004 et sur un exposé réalisé à l’IUFM de Reims en juin 2003 (Integrating Technologies into Mathematics Education). Nous y présentons divers systèmes de numération du point de vue de la théorie des langages formels. On s’attache dès lors à mettre en lumière les liens éventuels entre propriétés arithmétiques des nombres et propriétés syntaxiques de leurs représentations. La première partie de ce texte introduit en particulier la notion d’automate et quelques unes de ses applications. [less ▲]

Detailed reference viewed: 32 (3 ULiège)
Full Text
See detailAbstract numeration systems and tilings
Berthé; Rigo, Michel ULiege

in Lecture Notes in Computer Science (2005), 3618

An abstract numeration system is a triple S = (L, Sigma, <) where (Z, <) is a totally ordered alphabet and L a regular language over Z; the associated numeration is defined as follows: by enumerating the ... [more ▼]

An abstract numeration system is a triple S = (L, Sigma, <) where (Z, <) is a totally ordered alphabet and L a regular language over Z; the associated numeration is defined as follows: by enumerating the words of the regular language L over Z with respect to the induced genealogical ordering, one obtains a one-to-one correspondence between N 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 athe 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]. [less ▲]

Detailed reference viewed: 44 (5 ULiège)
Full Text
See detailAbstract beta-expansion and ultimately periodic representations
Rigo, Michel ULiege; Steiner, Wolfgang

in Journal de Théorie des Nombres de Bordeaux (2005), 17

For abstract numeration systems built on exponential regular languages (including those coming from substitutions), we show that the set of real numbers having an ultimately periodic representation is ... [more ▼]

For abstract numeration systems built on exponential regular languages (including those coming from substitutions), we show that the set of real numbers having an ultimately periodic representation is $\mathbb{Q}(\beta)$ if the dominating eigenvalue $\beta>1$ of the automaton accepting the language is a Pisot number. Moreover, if $\beta$ is neither a Pisot nor a Salem number, then there exist points in $\mathbb{Q}(\beta)$ which do not have any ultimately periodic representation. [less ▲]

Detailed reference viewed: 16 (2 ULiège)
Full Text
See detailDecidability questions related to abstract numeration systems
Honkala, Juha; Rigo, Michel ULiege

in Discrete Mathematics (2004), 285(1-3), 329-333

We show that some decidability questions concerning recognizable sets of integers for abstract numeration systems are equivalent to classical problems related to HD0L systems. It turns out that these ... [more ▼]

We show that some decidability questions concerning recognizable sets of integers for abstract numeration systems are equivalent to classical problems related to HD0L systems. It turns out that these problems are decidable when the sets of representations of the integers are slender regular languages. (C) 2004 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 31 (0 ULiège)
Full Text
See detailReal numbers having ultimately periodic representations in abstract numeration systems
Lecomte, Pierre ULiege; Rigo, Michel ULiege

in Information and Computation (2004), 192(1), 57-83

Using a genealogically ordered infinite regular language, we know how to represent an interval of R. Numbers having an ultimately periodic representation play a special role in classical numeration ... [more ▼]

Using a genealogically ordered infinite regular language, we know how to represent an interval of R. Numbers having an ultimately periodic representation play a special role in classical numeration systems. The aim of this paper is to characterize the numbers having an ultimately periodic representation in generalized systems built on a regular language. The syntactical properties of these words are also investigated. Finally, we show the equivalence of the classical theta-expansions with our generalized representations in some special case related to a Pisot number theta. (C) 2004 Elsevier Inc. All rights reserved. [less ▲]

Detailed reference viewed: 17 (2 ULiège)
Full Text
See detailCharacterizing Simpler recognizable sets of integers
Rigo, Michel ULiege

in Studia Logica (2004), 76

For a given numeration system U, a set X of integers is said to be U-star-free if the language of the normalized U-representations of the elements in X is star-free. Adapting a result of McNaughton and ... [more ▼]

For a given numeration system U, a set X of integers is said to be U-star-free if the language of the normalized U-representations of the elements in X is star-free. Adapting a result of McNaughton and Papert, we give a first-order logical characterization of these sets for various numeration systems including integer base systems and the Fibonacci system. For k-ary systems, the problem of the base dependence of this property is also studied. Finally, the case of k-adic systems is developed. [less ▲]

Detailed reference viewed: 13 (0 ULiège)
Full Text
See detailThe commutative closure of a binary slip-language is context-free: a new proof
Rigo, Michel ULiege

in Discrete Applied Mathematics (2003), 131(3), 665-672

Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic <N, +>, we give a new proof that the commutative closure of a slip-language over a two ... [more ▼]

Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic <N, +>, we give a new proof that the commutative closure of a slip-language over a two letters alphabet is context-free. (C) 2003 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 25 (4 ULiège)
Full Text
See detailAdditive functions with respect to numeration systems on regular languages
Grabner, Peter J.; Rigo, Michel ULiege

in Monatshefte fur Mathematik (2003), 139(3), 205-219

Asymptotic formulae for the summatory function of additive arithmetic functions related to numeration systems given by regular languages are derived.

Detailed reference viewed: 15 (2 ULiège)
Full Text
See detailConstruction of regular languages and recognizability of polynomials
Rigo, Michel ULiege

in Discrete Mathematics (2002), 254(1-3), 485-496

A generalization of numeration systems in which NI is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite regular language. We show that if P is an element ... [more ▼]

A generalization of numeration systems in which NI is recognizable by finite automata can be obtained by describing a lexicographically ordered infinite regular language. We show that if P is an element of Q[x] is a polynomial such that P(N) subset of N then there exists a numeration system in which the set of representations of P(N) is regular. The main issue is to construct a regular language with a complexity function equals to P(n + 1) - P(n) for n large enough. (C) 2002 Elsevier Science B.V. All rights reserved. [less ▲]

Detailed reference viewed: 18 (5 ULiège)
Full Text
See detailCharacterizing simpler recognizable sets of integers
Rigo, Michel ULiege

in Lecture Notes in Computer Science (2002), 2420

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

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

Detailed reference viewed: 15 (5 ULiège)
Full Text
See detailOn the representation of real numbers using regular languages
Lecomte, Pierre ULiege; Rigo, Michel ULiege

in Theory of Computing Systems (2002), 35(1, JAN-FEB), 13-38

Using a lexicographically ordered regular language, we show how to represent an interval of R. We determine exactly the possible representations of any element in this interval and study the function ... [more ▼]

Using a lexicographically ordered regular language, we show how to represent an interval of R. We determine exactly the possible representations of any element in this interval and study the function which maps a representation onto its numerical value. We make explicit the relationship between the convergence of finite words to an infinite word and the convergence of the corresponding approximations to a real number. [less ▲]

Detailed reference viewed: 54 (10 ULiège)
Full Text
See detailMore on generalized automatic sequences
Rigo, Michel ULiege; Maes, Arnaud

in Journal of Automata, Languages and Combinatorics (2002), 7

We give some generalizations of $k$-automatic sequences replacing the $k$-ary system by an abstract numeration system on a regular language. We study some of the closure properties of these sequences and ... [more ▼]

We give some generalizations of $k$-automatic sequences replacing the $k$-ary system by an abstract numeration system on a regular language. We study some of the closure properties of these sequences and the possible extension to the multidimensional case or to infinite alphabets. The equivalence of these sequences and morphic predicates is given and the relationship to recognizability is also investigated. [less ▲]

Detailed reference viewed: 44 (10 ULiège)
Full Text
See detailAbstract numeration systems on a regular languages and recognizability
Rigo, Michel ULiege

Doctoral thesis (2001)

Detailed reference viewed: 117 (10 ULiège)
Full Text
See detailNumeration systems on a regular language : Arithmetic operations, Recognizability and Formal power series
Rigo, Michel ULiege

in Theoretical Computer Science (2001), 269

Generalizations of numeration systems in which \(\N\) is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language \(L\subset \Sigma^*\). For ... [more ▼]

Generalizations of numeration systems in which \(\N\) is recognizable by a finite automaton are obtained by describing a lexicographically ordered infinite regular language \(L\subset \Sigma^*\). 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 \(\Theta (n^l)\) (resp. if \(L\) is the complement of a polynomial language), then multiplication by \(\lambda\in \N\) preserves recognizability only if \(\lambda=\beta^{l+1}\) (resp. if \(\lambda\neq (\#\Sigma)^\beta\)) for some \(\beta\in \N\). Finally, we obtain sufficient conditions for the notions of recognizability for abstract systems and some positional number systems to be equivalent. [less ▲]

Detailed reference viewed: 31 (2 ULiège)
Full Text
See detailNumerations systems on a regular language
Lecomte, Pierre ULiege; Rigo, Michel ULiege

in Theory of Computing Systems (2001), 34

Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the lexicographic ordering. For ... [more ▼]

Generalizations of positional number systems in which N is recognizable by finite automata are obtained by describing an arbitrary infinite regular language according to the lexicographic ordering. For these systems of numeration, we show that ultimately periodic sets are recognizable. We also study translation and multiplication by constants as well as the order-dependence of the recognizability. [less ▲]

Detailed reference viewed: 39 (2 ULiège)
Full Text
See detailGeneralization of automatic sequences for numeration systems on a regular language
Rigo, Michel ULiege

in Theoretical Computer Science (2000), 244

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

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

Detailed reference viewed: 24 (3 ULiège)