Thèse Complexité des Langages Engendrés par des Automates de Substitution H/F - 33

Établissement : Université de Bordeaux
École doctorale : Mathématiques et Informatique
Laboratoire de recherche : LaBRI - Laboratoire Bordelais de Recherche en Informatique
Direction de la thèse : Vincent DELECROIX ORCID 000000029608782X
Début de la thèse : 2026-10-01
Date limite de candidature : 2026-05-04T23:59:59

Cette thèse se situe à la frontière de la combinatoire des mots et de la combinatoire énumérative. Le contexte général est celui de l'étude des langages formels sur un alphabet fini. On souhaite plus précisément étudier la fonction de complexité d'un tel langage. Dans le cas des langages réguliers ou donnés par des grammaires non-ambigües, les
fonction génératrices sont respectivement rationnelles ou algbériques. Le cadre de cette thèse s'intéresse aux langages engendrés par des automates de substitutions aussi appelés langages S-adiques. L'exemple prototypique d'un tel langage est celui des mots sturmiens. L'objectif est de déterminer des conditions suffisantes sur un langage engendré par un automate de substitutions qui permettent d'en déduire que sa fonction de complexité ait une asymptotique polynomiale. Les exemples qui viennent des échanges d'intervalles serviront de fils directeurs à cette étude.