Soutenance de thèse de Adeline Massuir
![](upload/docs/image/jpeg/2021-04/these_massuir.jpg)
Info
Le vendredi 30 avril 2021, Adeline MASSUIR présentera l'examen en vue de l’obtention du grade académique de Docteur en Sciences (Collège de doctorat en Mathématique) sous la direction de Michel RIGO.
Cette épreuve consistera en la défense publique d’une dissertation intitulée :
« Positional Numeration Systems: Ultimate Periodicity, Complexity and Automatic Sequences ».
Résumé
Cette dissertation est composée de trois parties distinctes, liées par des notions de complexité, que ce soit la complexité factorielle ou la complexité en nombre d’états. Nous étudions les systèmes de numération de position et les ensembles reconnaissables à travers des problèmes de décision ainsi que les suites automatiques.
La première partie est dédiée au problème suivant: étant donné un système de numération U et un automate fini acceptant les écritures en base U d’un ensemble X de naturels, peut-on décider si l’ensemble X est ultimement périodique (i.e. une union finie de progressions arithmétiques)? Nous démontrons que ce problème est décidable pour une grande classe de systèmes de numération définis à partir de suites linéaires récurrentes. Grâce à l’automate donné, nous bornons les périodes possibles pour X via une étude arithmétique de la suite linéaire récurrente, ainsi qu’à l’aide de méthodes p-adiques.
La deuxième partie est consacrée à l’ensemble des entiers positifs ou nuls dont l’écriture en base 2 contient un nombre pair de 1, appelé ensemble de Thue-Morse et noté T. Nous étudions l’automate minimal des écritures en base 2^p des ensembles de la forme mT+r, où m et p sont des entiers positifs et r un reste compris entre 0 et m-1. En particulier, nous donnons la complexité en états de tels ensembles. La méthode proposée est constructive et générale pour n’importe quel ensemble b-reconnaissable d’entiers. Comme application, nous obtenons une procédure pour décider si un ensemble 2^p-reconnaissable donné via un automate est un ensemble de la forme mT+r.
Finalement, dans la troisième partie, nous étudions des propriétés des suites automatiques basées sur des systèmes de numération de Parry et de Bertrand. Nous montrons que les suites Parry-automatiques ont, comme les suites Pisot-automatiques (et donc en particulier comme les suites b-automatiques) une complexité factorielle sous-linéaire. D’autre part, nous exhibons une suite Bertrand-automatique dont la complexité factorielle est quadratique. Nous démontrons également que, contrairement aux suites Pisot-automatiques, l’image d’une suite Parry-automatique par un morphisme uniforme n’est plus nécessairement Parry-automatique. Il en va de même pour la suppression périodique de lettres. Enfin, nous donnons la généralisation aux suites multidimensionnelles d’un résultat bien connu: une suite est U-automatique si et seulement si son U-noyau est fini, U étant tel que le langage de la numération est régulier.
Le Jury sera composé de :
M. J. LEROY (Président), Mme et MM. E. CHARLIER (Secrétaire), J. HONKALA (University of Turku), V. MARSAULT (Université Paris-Est Marne-la-Vallée), M. RIGO (Promoteur), E. ROWLAND (Hofstra University).
En raison de l’épidémie du coronavirus, cette défense de thèse se fera en visioconférence via Lifesize.
Le lien public pour accéder à la défense est :
Adresse : https://call.lifesizecloud.com/8724946
Mot de passe : 3004