Browse ORBi by ORBi project

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

Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets Lacroix, Anne Doctoral thesis (2013) In this thesis, we study and answer several questions concerning recognizability of integer sets by finite automata. Each particular problem is the focus of a chapter. First, we study the recognizability ... [more ▼] In this thesis, we study and answer several questions concerning recognizability of integer sets by finite automata. Each particular problem is the focus of a chapter. First, we study the recognizability of the so-called self-generating sets, initially introduced by C. Kimberling. In the second part, we study the syntactic complexity of any ultimately periodic set and we use our results to give an alternative decision procedure for a well-known decidability problem. Next, we give bounds on the automaticity of three different languages: the language of primitive words over a finite alphabet, the language of unbordered words over a finite alphabet and the language of representations of monic irreducible polynomials over a finite fields. Finally, we characterize the multidimensional sets that are recognizable in all abstract numeration systems. [less ▲] Detailed reference viewed: 116 (31 ULg)Syntactic complexity of ultimately periodic sets of integers and application to a decision procedure Lacroix, Anne ; ; Rigo, Michel et al in Fundamenta Informaticae (2012), 116 We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any ... [more ▼] We compute the cardinality of the syntactic monoid of the language 0* rep_b(mN) made of base b expansions of the multiples of the integer m. We also give lower bounds for the syntactic complexity of any (ultimately) periodic set of integers written in base b. We apply our results to a well studied problem: decide whether or not a b-recognizable set of integers is ultimately periodic. [less ▲] Detailed reference viewed: 91 (12 ULg)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)On the Recognizability of Self-Generating Sets ; Lacroix, Anne ; Rigo, Michel in Journal of Integer Sequences (2010), 13 Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of ... [more ▼] Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of integers containing I and satisfying f(X)\subseteq X for all f in F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k_i are multiplicatively independent, then X is not k-recognizable for any k>=2. [less ▲] Detailed reference viewed: 31 (9 ULg)On the Recognizability of Self-Generating Sets Kärki, Tomi ; Lacroix, Anne ; Rigo, Michel in Lecture Notes in Computer Science (2009), 5734 Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of ... [more ▼] Let I be a finite set of integers and F be a finite set of maps of the form n->k_i n + l_i with integer coefficients. For an integer base k>=2, we study the k-recognizability of the minimal set X of integers containing I and satisfying f(X)\subseteq X for all f in F. In particular, solving a conjecture of Allouche, Shallit and Skordev, we show under some technical conditions that if two of the constants k_i are multiplicatively independent, then X is not k-recognizable for any k>=2. [less ▲] Detailed reference viewed: 59 (17 ULg) |
||