Michel Rigo (ULiège) : Combinatoire des mots : résultats classiques et avancées récentes

Thursday 19 Apr 2018, 16:30 → 18:30 Europe/Brussels

CYCL01 (MdeHemptinne)

Résumé Dans cet exposé ne nécessitant aucun prérequis, je présenterai quelques grands thèmes issus de la combinatoire des mots (i.e., des suites prenant leurs valeurs dans un ensemble fini de symboles) et leurs possibles applications en théorie des nombres, en dynamique symbolique ou en géométrie discrète. En guise d'illustration, considérons le problème suivant. Un carré est la répétition de deux facteurs consécutifs identiques. Ainsi, le mot "entente" débute par le carré (ent)^2 et se aussi termine par le carré (nte)^2. Etant donné un alphabet de taille fixée, on souhaite construire un mot, le plus long possible, évitant un motif particulier. On se rend aisément compte qu'avec deux lettres, tout mot de longueur au moins 4 contient un carré. Par contre, il est possible de définir une suite infinie, à valeurs dans {0,1,2}, ne contenant aucun carré. Ces questions centrales d'évitabilité se retrouvent, dès le début du XXe siècle, dans les travaux d'Axel Thue et ont de multiples déclinaisons récentes. Dans un second temps, je me concentrerai sur une large famille de mots infinis, les suites k-automatiques. Elles sont obtenues à partir d'écritures en base entière k et d'un modèle de calcul des plus simples: un automate fini déterministe. On dispose alors d'une caractérisation logique de ces suites donnée par le théorème de Büchi. Dans ce cadre, de nombreux problèmes de nature combinatoire peuvent être décidés formellement de façon automatique. Nous montrerons les avantages de cette approche mais aussi ses limites.