Reference : Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity an...
Dissertations and theses : Doctoral thesis
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/147877
Contributions to Recognizability: Self-generating Sets, Decidability, Automaticity and Multidimensional Sets
English
Lacroix, Anne mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
28-May-2013
Université de Liège, ​Liège, ​​Belgique
Docteur en Sciences
Rigo, Michel mailto
Lecomte, Pierre mailto
Charlier, Emilie mailto
Hansoul, Georges mailto
Berthé, Valérie mailto
Allouche, Jean-Paul mailto
[en] Recognizable sets of integers ; Self-generating sets ; Automaticity ; Multidimensional sets of integers ; Positional and abstract numeration systems ; Syntactic complexity ; Automata and formal language theory
[fr] 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
[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.
http://hdl.handle.net/2268/147877

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
these_Lacroix_Anne.pdfAuthor postprint820.88 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.