Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets

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.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