Sur la complexité des mots q∞-automatiques
Institution:
Aix-Marseille 2Disciplines:
Directors:
Abstract EN:
In this thesis, we study a class of infinite words on a finite alphabet, generated by q-automata with countable states set, for an integer q ≥ 2. Those words, called q∞-automatic words are images by some « admissibles » morphisms of fixed points of substitutions of constant length q over countable alphabets. In this sense, thoses words can be viewed as a generalisation of automatic words. We show that the complexity function p of the (2d)∞-automatic word generated by the automaton related to regular random walk on Zd satisfies p(n) = O(n logd+1 2d n). Mo-reover, in the one-dimension case, the function n log2 2 n is an equivalent of the complexity function. This result can be generalized to q∞-automatic words generated by automata related to more general random walks on Zd by the relation p(n) = O(n logq+1 q n). In the more general case of q∞-automatic words generated by bounded degree auto- mata, we prouve that the complexity function is at most a polynomial function. We show how this result can be improved on examples, to obtain a thiner majoration of the com- plexity function order of growth. Moreover, on one exemple related to the Dyck language over two types of parenthesis, we obtain the exact complexity function order of growth. We also give a polynomial majoration of the complexity function for q∞-automatic words generated by monotone automata.
Abstract FR:
L’objet de cette thèse est l’étude de mots infinis, à valeurs dans un alphabet fini, engendrés par des q-automates dont l’ensemble des états est dénombrable (q est un nombre entier supérieur ou égal à 2). Ces mots, appelés mots q∞-automatiques, sont les images par morphismes « admissibles » de points fixes de substitutions de longueur constante sur un alphabet dénombrable et peuvent être perçus comme une généralisation des mots automatiques. Nous montrons que la fonction de complexité p du mot (2d)∞-automatique engendré par l’automate associé à la marche aléatoire régulière dans Zd vérifie p(n) = O(n logd+1 2d n). Lorsque d = 1, on montre que la fonction n log2 2 n est un équivalent de la fonction de complexité. Nous verrons également que l’on peut généraliser cette majoration de l’ordre de grandeur de la fonction de complexité aux mots q∞-automatiques engendrés par les automates associé aux marches aléatoires moins régulières dans Zd par la relation p(n) = O(n logq+1 q n). Dans le cadre plus général des mots q∞-automatiques engendrés par des automates de degré borné, nous montrons que la fonction de complexité est au plus polynomiale. Nous verrons, sur des exemples, comment améliorer ce résultat pour obtenir une majoration plus fine de l’ordre de grandeur de la fonction de complexité. Sur un exemple, associé au langage de Dyck sur deux types de parenthèses, on obtient même l’ordre de croissance exact de la complexité. Nous donnons également un résultat de majoration polynomiale de l’ordre de grandeur de la fonction de complexité pour les mots q∞-automatiques engendrés par des automates monotones.