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.