Publications of Michel Rigo     Results 101-120 of 120.   1 2 3 4 5 6 Syntactictal and automatic properties of sets of polynomials over finite fieldsRigo, Michel Conference (2006, October)Detailed reference viewed: 26 (1 ULg) Abstract numeration systems : a survey.Rigo, Michel Conference (2006, August)Detailed reference viewed: 39 (4 ULg) 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: 25 (2 ULg) 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: 28 (1 ULg) 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: 32 (3 ULg) 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: 44 (5 ULg) 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: 16 (2 ULg) 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 ULg) 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: 16 (2 ULg) 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: 13 (0 ULg) 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 ULg) 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 ULg) Construction of regular languages and recognizability of polynomialsRigo, Michel in Discrete Mathematics (2002), 254(1-3), 485-496A 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 ULg) Characterizing simpler recognizable sets of integersRigo, Michel in Lecture Notes in Computer Science (2002), 2420For 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 ULg) On the representation of real numbers using regular languagesLecomte, Pierre ; Rigo, Michel in Theory of Computing Systems (2002), 35(1, JAN-FEB), 13-38Using 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: 47 (10 ULg) More on generalized automatic sequencesRigo, Michel ; Maes, Arnaudin Journal of Automata, Languages and Combinatorics (2002), 7We 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 ULg) Abstract numeration systems on a regular languages and recognizabilityRigo, Michel Doctoral thesis (2001)Detailed reference viewed: 109 (10 ULg) Numeration systems on a regular language : Arithmetic operations, Recognizability and Formal power seriesRigo, Michel in Theoretical Computer Science (2001), 269Generalizations 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 ULg) Numerations systems on a regular languageLecomte, Pierre ; Rigo, Michel in Theory of Computing Systems (2001), 34Generalizations 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 ULg) Generalization of automatic sequences for numeration systems on a regular languageRigo, Michel in Theoretical Computer Science (2000), 244Let 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 ULg)