References of "Lacroix, Anne"
     in
Bookmark and Share    
Full Text
See detailContributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets
Lacroix, Anne ULg

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: 80 (27 ULg)
Full Text
Peer Reviewed
See detailSyntactic complexity of ultimately periodic sets of integers and application to a decision procedure
Lacroix, Anne ULg; Rampersad, Narad; Rigo, Michel ULg 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: 52 (5 ULg)
Full Text
Peer Reviewed
See detailMulti-dimensional sets recognizable in all abstract numeration systems
Charlier, Emilie ULg; Lacroix, Anne ULg; Rampersad, Narad ULg

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: 77 (22 ULg)
Full Text
Peer Reviewed
See detailOn the Recognizability of Self-Generating Sets
Kärki, Tomi; Lacroix, Anne ULg; Rigo, Michel ULg

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: 29 (9 ULg)
Full Text
Peer Reviewed
See detailOn the Recognizability of Self-Generating Sets
Kärki, Tomi ULg; Lacroix, Anne ULg; Rigo, Michel ULg

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: 53 (16 ULg)