Reference : Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Autom...
Dissertations and theses : Doctoral thesis
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/8631
Abstract Numeration Systems : Recognizability, Decidability, Multidimensional S-Automatic Words, and Real Numbers
English
[en] Systèmes de numération abstraits : reconnaissabilité, décidabilité, mots S-automatiques multidimensionnels et nombres réels
Charlier, Emilie mailto [Université de Liège - ULg > > > Doct. sc. (math. - Bologne)]
7-Dec-2009
Université de Liège, ​Liège, ​​Belgique
Doctorat en sciences
160
Rigo, Michel mailto
Lecomte, Pierre mailto
Hansoul, Georges mailto
Berthé, Valérie mailto
Boigelot, Bernard mailto
Sakarovitch, Jacques mailto
[en] positional and abstract numeration systems ; automata and formal language theory ; recognizable sets of numbers ; arithmetic operations ; generalized multidimensional automatic sequences ; multidimensional non uniform morphisms ; combinatorics on words ; linear recurrence sequences ; real numbers
[fr] numérations de position et abstraites ; théorie des automates et des langages formels ; ensembles de nombres reconnaissables ; opérations arithmétiques ; suites automatiques généralisées multidimensionnelles ; morphismes non uniformes multidimensionnels ; combinatoire des mots ; suites linéaires récurrentes ; nombres réels
[en] In this dissertation we study and we solve several questions regarding abstract numeration systems. Each particular problem is the focus of a chapter. The first problem concerns the study of the preservation of recognizability under multiplication by a constant in abstract numeration systems built on polynomial regular languages. The second is a decidability problem, which has been already studied notably by J. Honkala and A. Muchnik and which is studied here for two new cases: the linear positional numeration systems and the abstract numeration systems. Next, we focus on the extension to the multidimensional setting of a result of A. Maes and M. Rigo regarding S-automatic infinite words. Finally, we propose a formalism to represent real numbers in the general framework of abstract numeration systems built on languages that are not necessarily regular. We end by a list of open questions in the continuation of the present work.
[fr] Dans cette dissertation, nous étudions et résolvons plusieurs questions autour des systèmes de numération abstraits. Chaque problème étudié fait l'objet d'un chapitre. Le premier concerne l'étude de la conservation de la reconnaissabilité par la multiplication par une constante dans des systèmes de numération abstraits construits sur des langages réguliers polynomiaux. Le deuxième est un problème de décidabilité déjà étudié notamment par J. Honkala et A. Muchnik et ici décliné en deux nouvelles versions : les systèmes de numération de position linéaires et les systèmes de numération abstraits. Ensuite, nous nous penchons sur l'extension au cas multidimensionnel d'un résultat d'A. Maes et de M. Rigo à propos des mots infinis S-automatiques. Finalement, nous proposons un formalisme de la représentation des nombres réels dans le cadre général des systèmes de numération abstraits basés sur des langages qui ne sont pas nécessairement réguliers. Nous terminons par une liste de questions ouvertes dans la continuité de ce travail.
http://hdl.handle.net/2268/8631

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
mathese.pdfNo commentaryAuthor postprint1.17 MBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.