Publications of Michel Rigo     Results 101-120 of 128.   1 2 3 4 5 6 7   Combinatorics, Automata and Number Theory 2006Berthé, Valérie; Lecomte, Pierre ; Rigo, Michel in Theoretical Computer Science (2008), 391Detailed reference viewed: 30 (9 ULiège) Abstract numeration systems on bounded languages and multiplication by a constantCharlier, Emilie ; Rigo, Michel ; Steiner, Wolfgangin INTEGERS: Electronic Journal of Combinatorial Number Theory (2008), 8(1-A35), 1-19A 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: 42 (7 ULiège) About frequencies of letters in generalized automatic sequencesNicolay, Samuel ; Rigo, Michel in Theoretical Computer Science (2007), 374(1-3), 25-40We 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: 21 (6 ULiège) Distribution of additive functions with respect to numeration systems on regular languagesGrabner, Peter J.; Rigo, Michel in Theory of Computing Systems (2007), 40(3), 205-223We study the distribution of values of additive functions related to numeration systems defined via regular languages.Detailed reference viewed: 24 (6 ULiège) Odometers on regular languagesBerthé; Rigo, Michel in Theory of Computing Systems (2007), 40(1), 1-31Odometers 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: 28 (5 ULiège) Pirates informatiques et mathématique modulaireRigo, Michel 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: 86 (11 ULiège) special issue dedicated to the tenth Journées montoises d'informatique théorique''Bruyère, Véronique; Rigo, Michel in Discrete Mathematics & Theoretical Computer Science (2007), 9(2), 1Detailed reference viewed: 18 (5 ULiège) On the cost and complexity of the successor functionBerthé, Valérie; Frougny, Christiane; Rigo, Michel et alin 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: 15 (1 ULiège) Syntactictal and automatic properties of sets of polynomials over finite fieldsRigo, Michel Conference (2006, October)Detailed reference viewed: 36 (1 ULiège) Abstract numeration systems : a survey.Rigo, Michel Conference (2006, August)Detailed reference viewed: 45 (4 ULiège) A note on syndeticity, recognizable sets and Cobham's theoremRigo, Michel ; Waxweiler, Laurent in Bulletin of the European Association for Theoretical Computer Science (2006), 88In 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: 27 (2 ULiège) Structural properties of bounded languages with respect to multiplication by a constantCharlier, Emilie ; Rigo, Michel 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: 27 (1 ULiège) Automates et systèmes de numérationRigo, Michel in Bulletin de la Société Royale des Sciences de Liège (2005), 73Ce 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: 33 (3 ULiège) Abstract numeration systems and tilingsBerthé; Rigo, Michel in Lecture Notes in Computer Science (2005), 3618An 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: 42 (5 ULiège) Abstract beta-expansion and ultimately periodic representationsRigo, Michel ; Steiner, Wolfgangin Journal de Théorie des Nombres de Bordeaux (2005), 17For 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: 17 (2 ULiège) Decidability questions related to abstract numeration systemsHonkala, Juha; Rigo, Michel in Discrete Mathematics (2004), 285(1-3), 329-333We 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) Real numbers having ultimately periodic representations in abstract numeration systemsLecomte, Pierre ; Rigo, Michel in Information and Computation (2004), 192(1), 57-83Using 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) Characterizing Simpler recognizable sets of integersRigo, Michel in Studia Logica (2004), 76For 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: 14 (0 ULiège) The commutative closure of a binary slip-language is context-free: a new proofRigo, Michel in Discrete Applied Mathematics (2003), 131(3), 665-672Using original arguments about sets of integers satisfying some first-order formula of the Presburger arithmetic , 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 , 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) Additive functions with respect to numeration systems on regular languagesGrabner, Peter J.; Rigo, Michel in Monatshefte fur Mathematik (2003), 139(3), 205-219Asymptotic 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)