Recognizable sets of integers; Self-generating sets; Automaticity; Multidimensional sets of integers; Positional and abstract numeration systems; Syntactic complexity; Automata and formal language theory; Ensembles reconnaissables d'entiers; Ensembles auto-générés; Automaticité; Ensemble multidimensionnels d'entiers; Systèmes de numération positionnels et abstraits; Complexité syntaxique; Automates et théorie des langages formels
Abstract :
[en] 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. [fr] Dans cette thèse, nous étudions et répondons à plusieurs questions concernant le caractère reconnaissable d'ensembles d'entiers par automate fini. Chaque problème considéré fait l'objet d'un chapitre. Premièrement, nous étudions le caractère reconnaissable des ensembles auto-générés, introduits initialement par C. Kimberling. Dans la deuxième partie, nous étudions la complexité syntaxique des ensemble ultimement périodiques et nous utilisons nos résultats pour donner une procédure de décision alternative à un problème de décision bien connu. Ensuite, nous donnons des bornes pour l'automaticité de trois langages différents : le langage des mots primitifs sur un alphabet fini, le langage des mots sans bord sur un alphabet fini et le langage des représentations des polynômes moniques irréductibles sur un champ fini. Finalement, nous caractérisons les ensembles multidimensionnels qui sont reconnaissables dans tout système de numération abstrait.
Disciplines :
Mathematics
Author, co-author :
Lacroix, Anne ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets
Defense date :
28 May 2013
Institution :
ULiège - Université de Liège
Degree :
Docteur en Sciences
Promotor :
Rigo, Michel ; Université de Liège - ULiège > Département de mathématique
President :
Lecomte, Pierre ; Université de Liège - ULiège > Département de mathématique
