Doctoral thesis (Dissertations and theses)
Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences
Massuir, Adeline
2021
 

Files


Full Text
These-Massuir.pdf
Author preprint (2.02 MB)
Download
Annexes
Defense.pdf
Publisher postprint (480.61 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
numeration system; decidability; ultimate periodicity; automata theory; regular language; automatic sequence; Thue-Morse set; integer base
Abstract :
[en] This dissertation thesis is made up of three distinct parts, connected especially by complexity notion, factorial complexity as well as state complexity. We study positional numeration systems and recognizable sets through decision problems and automatic sequences. The first part is devoted to the following problem: given a numeration system U and a finite automaton accepting U-representations of a set X ⊆ N, can we decide whether the set X is ultimately periodic (i.e. a finite union of arithmetic progressions)? We prove that this problem is decidable for a large class of numeration systems based on linear recurrent sequences. Thanks to the given automaton, we bound the possible periods of X via an arithmetical study of the linear recurrent sequence, as well as p-adic methods. The second part is dealing with the set of non-negative integers whose base-2 representation contains an even number of 1, called the Thue-Morse set and denoted by T. We study of the minimal automaton of the base-2^p expansions of sets of the form mT+r, where m and p are positive integers and r a remainder between 0 and m−1. In particular, we give the state complexity of such sets. The proposed method is constructive and general for any b-recognizable set of integers. As an application, we get a procedure to decide whether a 2^p-recognizable set given via an automaton is a set of the form mT+r. Finally, in the third part, we study properties of automatic sequences based on Parry and Bertrand numeration systems. We show that Parry-automatic sequences, like Pisot-automatic sequences (and thus in particular like b-automatic sequences) have a sublinear factor complexity. Furthermore, we exhibit a Bertrand-automatic sequence whose factor complexity is quadratic. We also prove that, contrarily to Pisot-automatic sequences, the image of a Parry-automatic sequence under a uniform morphism is not always a Parry-automatic sequence. The same happens for periodic deletion of letters. Last, we give the generalization to multidimensional sequences of a well-known result: a sequence is U-automatic if and only if its U-kernel is finite, U being such that the numeration language is regular.
Disciplines :
Mathematics
Author, co-author :
Massuir, Adeline ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences
Defense date :
30 April 2021
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 :
Leroy, Julien ;  Université de Liège - ULiège > Mathematics
Secretary :
Charlier, Emilie  ;  Université de Liège - ULiège > Mathematics
Jury member :
Honkala, Juha
Marsault, Victor
Rowland, Eric
Available on ORBi :
since 29 March 2021

Statistics


Number of views
178 (45 by ULiège)
Number of downloads
123 (25 by ULiège)

Bibliography


Similar publications



Contact ORBi