References of "Rigo, Michel"
     in
Bookmark and Share    
Full Text
See detailLa matrice cachée de Google
Rigo, Michel ULg

Learning material (2008)

Inutile de le présenter : Google est le moteur de recherche le plus connu et le plus utilisé au monde. Mais comment les concepteurs de Google font-ils pour classer les milliers de pages se rapportant à un ... [more ▼]

Inutile de le présenter : Google est le moteur de recherche le plus connu et le plus utilisé au monde. Mais comment les concepteurs de Google font-ils pour classer les milliers de pages se rapportant à un mot-clé donné, de façon telle que les pages les plus représentatives occupent toujours les premières positions du classement ? Ce tour de force repose sur de véritables résultats mathématiques combinant théorie des graphes et algèbre linéaire. [less ▲]

Detailed reference viewed: 264 (8 ULg)
Full Text
Peer Reviewed
See detailAbout frequencies of letters in generalized automatic sequences
Nicolay, Samuel ULg; Rigo, Michel ULg

in Theoretical Computer Science (2007), 374(1-3), 25-40

We present some asymptotic results about the frequency of a letter appearing in a generalized unidimensional automatic sequence. Next, we study multidimensional generalized automatic sequences and the ... [more ▼]

We present some asymptotic results about the frequency of a letter appearing in a generalized unidimensional automatic sequence. Next, we study multidimensional generalized automatic sequences and the corresponding frequencies. (C) 2006 Elsevier B.V. All rights reserved. [less ▲]

Detailed reference viewed: 19 (6 ULg)
Full Text
Peer Reviewed
See detailDistribution of additive functions with respect to numeration systems on regular languages
Grabner, Peter J.; Rigo, Michel ULg

in Theory of Computing Systems (2007), 40(3), 205-223

We study the distribution of values of additive functions related to numeration systems defined via regular languages.

Detailed reference viewed: 25 (5 ULg)
Full Text
Peer Reviewed
See detailOdometers on regular languages
Berthé; Rigo, Michel ULg

in Theory of Computing Systems (2007), 40(1), 1-31

Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on ... [more ▼]

Odometers or "adding machines" are usually introduced in the context of positional numeration systems built on a strictly increasing sequence of integers. We generalize this notion to systems defined on an arbitrary infinite regular language. In this latter situation, if (A, <) is a totally ordered alphabet, then enumerating the words of a regular language L over A with respect to the induced genealogical ordering gives a one-to-one correspondence between N and L. In this general setting the odometer is not defined on a set of sequences of digits but on a set of pairs of sequences where the first (resp. the second) component of the pair is an infinite word over A (resp. an infinite sequence of states of the minimal automaton of L). We study some properties of the odometer such as continuity, injectivity, surjectivity, minimality,... We then study some particular cases: we show the equivalence of this new function with the classical odometer built upon a sequence of integers whenever the set of greedy representations of all the integers is a regular language; we also consider substitution numeration systems as well as the connection with beta-numerations. [less ▲]

Detailed reference viewed: 21 (5 ULg)
Full Text
Peer Reviewed
See detailspecial issue dedicated to the tenth ``Journées montoises d'informatique théorique''
Bruyère, Véronique; Rigo, Michel ULg

in Discrete Mathematics & Theoretical Computer Science (2007), 9(2), 1

Detailed reference viewed: 15 (5 ULg)
Full Text
See detailPirates informatiques et mathématique modulaire
Rigo, Michel ULg

Learning material (2007)

De nos jours, l'envoi de messages secrets requiert la manipulation de nombres ayant plus de cent chiffres décimaux. Nous illustrons une technique cryptographique standard (le RSA) dont la sécurité réside ... [more ▼]

De nos jours, l'envoi de messages secrets requiert la manipulation de nombres ayant plus de cent chiffres décimaux. Nous illustrons une technique cryptographique standard (le RSA) dont la sécurité réside dans le fait qu'il est "rapide", sur le plus banal des ordinateurs personnels, de calculer le produit de deux "grands" nombres (cela se compte au pire en secondes), alors que le temps nécessaire pour effectuer l'opération inverse de factorisation prend, dans l'état actuel des connaissances mathématiques, énormément plus de temps (que l'on pourrait estimer en milliards d'années même pour un super-calculateur !). [less ▲]

Detailed reference viewed: 60 (6 ULg)
Full Text
Peer Reviewed
See detailOn the cost and complexity of the successor function
Berthé, Valérie; Frougny, Christiane; Rigo, Michel ULg et al

in Arnoux, P.; Bédaride, N. (Eds.) Proceedings of WORDS 2007 (2007)

For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word ... [more ▼]

For a given numeration system, the successor function maps the representation of an integer n onto the representation of its successor n+1. In a general setting, the successor function maps the n-th word of a genealogically ordered language L onto the (n+1)-th word of L. We show that, if the ratio of the number of elements of length n + 1 over the number of elements of length n of the language has a limit b> 1, then the amortized cost of the successor function is equal to b/(b − 1). From this, we deduce the value of the amortized cost for several classes of numeration systems (integer base systems, canonical numeration systems associated with a Parry number, abstract numeration systems built on a rational language, and rational base numeration systems). [less ▲]

Detailed reference viewed: 14 (1 ULg)
Full Text
See detailSyntactictal and automatic properties of sets of polynomials over finite fields
Rigo, Michel ULg

Conference (2006, October)

Detailed reference viewed: 8 (1 ULg)
Full Text
See detailAbstract numeration systems : a survey.
Rigo, Michel ULg

Conference (2006, August)

Detailed reference viewed: 13 (2 ULg)
Full Text
Peer Reviewed
See detailStructural properties of bounded languages with respect to multiplication by a constant
Charlier, Emilie ULg; Rigo, Michel ULg

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: 21 (1 ULg)
Full Text
Peer Reviewed
See detailA note on syndeticity, recognizable sets and Cobham's theorem
Rigo, Michel ULg; Waxweiler, Laurent ULg

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: 21 (2 ULg)
Full Text
Peer Reviewed
See detailAutomates et systèmes de numération
Rigo, Michel ULg

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: 23 (2 ULg)
Full Text
Peer Reviewed
See detailAbstract beta-expansion and ultimately periodic representations
Rigo, Michel ULg; 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: 12 (2 ULg)
Full Text
Peer Reviewed
See detailAbstract numeration systems and tilings
Berthé; Rigo, Michel ULg

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: 31 (3 ULg)
Full Text
Peer Reviewed
See detailDecidability questions related to abstract numeration systems
Honkala, Juha; Rigo, Michel ULg

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: 22 (0 ULg)
Full Text
Peer Reviewed
See detailReal numbers having ultimately periodic representations in abstract numeration systems
Lecomte, Pierre ULg; Rigo, Michel ULg

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: 13 (2 ULg)
Full Text
Peer Reviewed
See detailCharacterizing Simpler recognizable sets of integers
Rigo, Michel ULg

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: 9 (0 ULg)
Full Text
Peer Reviewed
See detailThe commutative closure of a binary slip-language is context-free: a new proof
Rigo, Michel ULg

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: 17 (4 ULg)
Full Text
Peer Reviewed
See detailAdditive functions with respect to numeration systems on regular languages
Grabner, Peter J.; Rigo, Michel ULg

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: 9 (2 ULg)
Full Text
Peer Reviewed
See detailConstruction of regular languages and recognizability of polynomials
Rigo, Michel ULg

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: 13 (5 ULg)