Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »

En dynamique symbolique s’intersectent études des langages, des mots infinis et des structures dynamiques associées. Deux méthodes classiques de construction de ces objets coexistent. D’abord, la méthode de Thue construit un mot infini à l’aide d’une substitution (un morphisme de mots) : on itère la substitution sur une lettre initiale, et on considère le mot limite obtenu. Cette approche substitutive a été généralisée en autorisant l’utilisation de plusieurs substitutions, ce qui conduit à la notion de représentation S-adique. La seconde méthode pour générer des structures symboliques est de considérer les marches infinies sur un graphe étiqueté (ou ω-automate). Dans cette présentation, je considère des questions de décidabilité au croisement de ces deux points de vue : étant donné un ω-automate et un ensemble de substitutions, j’étudie l’ensemble des mots acceptés par l’ω-automate et défini par les substitutions, sa structure et sa vacuité.