Browse ORBi by ORBi project

- Background
- Content
- Benefits and challenges
- Legal aspects
- Functions and services
- Team
- Help and tutorials

Multi-dimensional sets recognizable in all abstract numeration systems Charlier, Emilie ; Lacroix, Anne ; Rampersad, Narad in RAIRO : Informatique Théorique et Applications = Theoretical Informatics and Applications (2012), 46(1), 51-65 We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional ... [more ▼] We prove that the subsets of N^d that are S-recognizable for all abstract numeration systems S are exactly the 1-recognizable sets. This generalizes a result of Lecomte and Rigo in the one-dimensional setting. [less ▲] Detailed reference viewed: 105 (25 ULg)Orbits of language operations: finiteness and upper bounds Charlier, Emilie Scientific conference (2011, August) Detailed reference viewed: 9 (1 ULg)Enumeration and decidable properties of automatic sequences Charlier, Emilie Conference (2011, July) Detailed reference viewed: 10 (1 ULg)Enumeration and decidable properties of automatic sequences Charlier, Emilie ; ; in Actes de Numération 2011 (2011, June) We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences ... [more ▼] We show that various aspects of k-automatic sequences such as having an unbordered factor of length n are both decidable and e ectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences de ned in terms of Pisot numeration systems. [less ▲] Detailed reference viewed: 22 (3 ULg)Finite orbits of language operations Charlier, Emilie Scientific conference (2011, May) Detailed reference viewed: 19 (3 ULg)Abstract numeration systems or decimation of languages Charlier, Emilie Scientific conference (2011, April) Detailed reference viewed: 15 (3 ULg)A numeration point of view on the HD0L periodicity problem Charlier, Emilie Scientific conference (2011, January) A HD0L system is a 5-tuple G = (∆, Γ, f, g, w) where • ∆ and Γ are alphabet; • f : ∆^∗ → ∆^∗ is a morphism; • g : ∆^∗ → Γ^∗ is a morphism; • w is a finite word over ∆. If w is a prefix of f(w) and if g(f ... [more ▼] A HD0L system is a 5-tuple G = (∆, Γ, f, g, w) where • ∆ and Γ are alphabet; • f : ∆^∗ → ∆^∗ is a morphism; • g : ∆^∗ → Γ^∗ is a morphism; • w is a finite word over ∆. If w is a prefix of f(w) and if g(f^ω(w)) is an infinite word over Γ, where f^ω(w) denotes the limit lim_{n→+∞}f^n(w), then we define the infinite word generated by G to be ω(G) = g(f^ω(w)). The question is to decide whether the infinite word ω(G) is ultimately periodic. This open problem is called the HD0L periodicity problem. It is not hard to see that we may assume that w is a letter. Furthermore, it is well known that we can assume that f is a non-erasing morphism and g is a coding. Therefore we will always consider that all these additional hypotheses hold. On the one hand, if f is uniform of length b, then ω(G) is b-automatic. In that particular case the problem is known to be decidable. Various proofs of this result have been given by several authors. On the other hand, in the general case, when f is not necessarily uniform, ω(G) is S-automatic for some abstract numeration system S. Therefore the HD0L periodicity problem is equivalent to the following problem involving numeration systems. Given an abstract numeration system S, is it decidable whether an S-recognizable set X ⊆ N is ultimately periodic? The numeration language L and the set X are given through DFAs accepting L and rep_S(X) respectively. Thanks to this numeration point of view, we can give decision procedures for large classes of numeration systems. In this talk, I will discuss some techniques used to provide such decision procedures. [less ▲] Detailed reference viewed: 23 (1 ULg)The minimal automaton recognizing mN in a linear numeration system Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Integers: Electronic Journal of Combinatorial Number Theory (2011), 11B(A4), 1-24 We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼] We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>1 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲] Detailed reference viewed: 133 (31 ULg)The growth function of S-recognizable sets Charlier, Emilie ; in Theoretical Computer Science (2011), 412(39), 5400-5408 A set X ⊆ N is S-recognizable for an abstract numeration system S, if the set rep_S (X) of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set ... [more ▼] A set X ⊆ N is S-recognizable for an abstract numeration system S, if the set rep_S (X) of its representations is accepted by a finite automaton. We show that the growth function of an S-recognizable set is always either Θ((log(n))^(c−df) n^f ) where c, d ∈ N and f ≥ 1, or Θ(n^r θ^(Θ(n^q))), where r, q ∈ Q with q ≤ 1. If the number of words of length n in the numeration language is bounded by a polynomial, then the growth function of an S-recognizable set is Θ(nr ), where r ∈ Q with r ≥ 1. Furthermore, for every r ∈ Q with r ≥ 1, we can provide an abstract numeration system S built on a polynomial language and an S-recognizable set such that the growth function of X is Θ(n^r ). For all positive integers k and ℓ, we can also provide an abstract numeration system S built on an exponential language and an S-recognizable set such that the growth function of X is Θ((log(n))^k n^ℓ). [less ▲] Detailed reference viewed: 21 (7 ULg)Enumeration and decidable properties of automatic sequences Charlier, Emilie ; ; in Lecture Notes in Computer Science (2011), 6795 We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related ... [more ▼] We show that various aspects of k-automatic sequences — such as having an unbordered factor of length n — are both decidable and effectively enumerable. As a consequence it follows that many related sequences are either k-automatic or k-regular. These include many sequences previously studied in the literature, such as the recurrence function, the appearance function, and the repetitivity index. We also give a new characterization of the class of k-regular sequences. Many results extend to other sequences defined in terms of Pisot numeration systems. [less ▲] Detailed reference viewed: 21 (4 ULg)Finite orbits of language operations Charlier, Emilie ; ; et al in Lecture Notes in Computer Science (2011), 6638 We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous ... [more ▼] We consider a set of natural operations on languages, and prove that the orbit of any language L under the monoid generated by this set is finite and bounded, independently of L. This generalizes previous results about complement, Kleene closure, and positive closure. [less ▲] Detailed reference viewed: 26 (3 ULg)Representing real numbers in a generalized numeration system Charlier, Emilie ; ; Rigo, Michel in Journal of Computer & System Sciences (2011), 77 We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers ... [more ▼] We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. [less ▲] Detailed reference viewed: 95 (23 ULg)S-automatic sets Charlier, Emilie Scientific conference (2010, December) In this talk, I will discuss some new properties of S-automatic sets. First I will show that a multidimensional set is S-automatic for all abstract numeration systems S if and only if it is 1-automatic ... [more ▼] In this talk, I will discuss some new properties of S-automatic sets. First I will show that a multidimensional set is S-automatic for all abstract numeration systems S if and only if it is 1-automatic. This result is surprising in the following sense: the class of multidimensional 1-automatic sets is a strict subclass of that of semi-linear sets. Hence, this result is not a generalization of the well-known result in integer base numeration systems: a multidimensional set is b-automatic for all integer bases b ≥ 1 if and only if it is semi-linear. Second I will describe the possible behaviors of the nth -term of an S-automatic set, depending on the growth function (i.e., the number of words of length n) of the numeration language. [less ▲] Detailed reference viewed: 26 (1 ULg)Criteria for recognizability in abstract numeration systems Charlier, Emilie Scientific conference (2010, October) In this talk, I will first shortly introduce abstract numeration systems. Then I will prove some first results I have regarding the growth function of recognizable sets. I will conjecture which functions ... [more ▼] In this talk, I will first shortly introduce abstract numeration systems. Then I will prove some first results I have regarding the growth function of recognizable sets. I will conjecture which functions can be the growth functions of recognizable sets in general, depending on the growth functions of the numeration language and of the sublanguage under consideration. [less ▲] Detailed reference viewed: 12 (0 ULg)State complexity of testing divisibility Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in McQuillan, Ian, Pighizzini, Giovanni (Ed.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems (2010, August) Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an ... [more ▼] Under some mild assumptions, we study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲] Detailed reference viewed: 75 (19 ULg)Structure of the minimal automaton of a numeration language Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Actes de LaCIM 2010 (2010, August) We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼] We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root beta>1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number beta. [less ▲] Detailed reference viewed: 101 (20 ULg)Representing real numbers in a generalized numeration system Charlier, Emilie Conference (2010, June) We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers ... [more ▼] We show how to represent an interval of real numbers in an abstract numeration system built on a language that is not necessarily regular. As an application, we consider representations of real numbers using the Dyck language. We also show that our framework can be applied to the rational base numeration systems. [less ▲] Detailed reference viewed: 19 (3 ULg)Structure of the minimal automaton of a numeration language and applications to state complexity Charlier, Emilie ; Rampersad, Narad ; Rigo, Michel et al in Actes des Journées Montoises d'Informatique Théorique (2010) We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly ... [more ▼] We study the structure of automata accepting the greedy representations of N in a wide class of numeration systems. We describe the conditions under which such automata can have more than one strongly connected component and the form of any such additional components. Our characterization applies, in particular, to any automaton arising from a Bertrand numeration system. Furthermore, we show that for any automaton A arising from a system with a dominant root > 1, there is a morphism mapping A onto the automaton arising from the Bertrand system associated with the number . Under some mild assumptions, we also study the state complexity of the trim minimal automaton accepting the greedy representations of the multiples of m>=2 for a wide class of linear numeration systems. As an example, the number of states of the trim minimal automaton accepting the greedy representations of mN in the Fibonacci system is exactly 2m^2. [less ▲] Detailed reference viewed: 56 (7 ULg)Multidimensional generalized automatic sequences and shape-symmetric morphic words Charlier, Emilie ; ; Rigo, Michel in Discrete Mathematics (2010), 310 An infinite word is S-automatic if, for all n>=0, its (n+1)st letter is the output of a deterministic automaton fed with the representation of n in the numeration system S. In this paper, we consider an ... [more ▼] An infinite word is S-automatic if, for all n>=0, its (n+1)st letter is the output of a deterministic automaton fed with the representation of n in the numeration system S. In this paper, we consider an analogous definition in a multidimensional setting and study its relation to the shapesymmetric infinite words introduced by Arnaud Maes. More precisely, for d>1, we show that a multidimensional infinite word x over a finite alphabet is S-automatic for some abstract numeration system S built on a regular language containing the empty word if and only if x is the image by a coding of a shape-symmetric infinite word. [less ▲] Detailed reference viewed: 59 (16 ULg)Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers Charlier, Emilie Doctoral thesis (2009) In this dissertation we study and we solve several questions regarding abstract numeration systems. Each particular problem is the focus of a chapter. The first problem concerns the study of the ... [more ▼] In this dissertation we study and we solve several questions regarding abstract numeration systems. Each particular problem is the focus of a chapter. The first problem concerns the study of the preservation of recognizability under multiplication by a constant in abstract numeration systems built on polynomial regular languages. The second is a decidability problem, which has been already studied notably by J. Honkala and A. Muchnik and which is studied here for two new cases: the linear positional numeration systems and the abstract numeration systems. Next, we focus on the extension to the multidimensional setting of a result of A. Maes and M. Rigo regarding S-automatic infinite words. Finally, we propose a formalism to represent real numbers in the general framework of abstract numeration systems built on languages that are not necessarily regular. We end by a list of open questions in the continuation of the present work. [less ▲] Detailed reference viewed: 172 (43 ULg) |
||