Activités de recherche depuis 2004
Mes activités de recherche, au sein de l'équipe SDMA du laboratoire MIS, portent sur les mots, finis et infinis, et les morphismes.
Un de mes principaux centres d'intérêt est l'étude des mots infinis sturmiens (écrits sur un alphabet binaire) et d'une de leur généralisations sur un alphabet quelconque : les mots épisturmiens. Ces mots ont de nombreuses propriétés remarquables, et l'un des outils permettant de les étudier efficacement sont les morphismes épisturmiens, sur lesquels ils peuvent se décomposer infiniment.
Depuis 2004, je m'intéresse à un problème issu de l'algorithmique du texte, celui de la quasipériodicité qui est une forme de répétition dans les mots. Les mots quasipériodiques sont ceux pour lesquels chaque lettre est facteur d'un mot appelé quasipériode. J'ai répondu, avec Gwénaël Richomme, à plusieurs questions concernant les mots infinis quasipériodiques, montrant entre autre qu'un mot sturmien n'est pas nécessairement quasipériodique, qu'un mot quasipériodique peut avoir une complexité exponentielle et caractérisant les quasipériodes du mot de Fibonacci, qui est un mot sturmien particulier. Ce travail a ensuite été complété par la caractérisation de tous les mots sturmiens quasipériodiques et par l'étude des liens entre les morphismes sturmiens et la quasipériodicité. Plus récemment, nous avons généralisé ces résultats aux mots épisturmiens en introduisant la normalisation de la décomposition morphique des mots épisturmiens, et en montrant que tout mot épisturmien possède une unique décomposition morphique normalisée. Ces résultats ont mené à une collaboration avec Amy Glen (UQAM, Montréal), qui avait parallélement travaillé sur le problème de la quasipériodicité en utilisant une autre approche. Cette collaboration a donné lieu en 2008 à deux articles, l'un portant sur les équivalences et la normalisation des mots directeurs des mots épisturmiens, l'autre résultant de la mise en commun de nos approches pour étudier la quasipériodicité et la lyndonicité des mots épisturmiens.
Depuis 2004, je participe également activement au groupe de travail « Mots : combinatoire et algorithmique », dont le but initial était de développer des interactions entre des membres de plusieurs équipes du LaRIA autour de problèmes d'algorithmique du texte et de modélisation par les mots. Ce groupe de travail s'est ensuite agrandi pour former le groupe "SDMA : Systèmes Dynamiques, Mots et Algorithmes", réunissant les équipes Mots, Systèmes Distribués et Calcul Parallèle de l'ancien laboratoire LaRIA, dont la fusion est effective depuis janvier 2008 au sein du laboratoire MIS. Ce groupe de travail m'a mené à une collaboration avec David Semé et Richard Groult (MIS), visant à paralléliser un algorithme de recherche de graine (c'est-à-dire de quasipériodes d'une extension d'un mot fini) sur le modèle LARPBS (Linear Array with Reconfigurable Pipeline Bus System). Nos résultats sont actuellement en cours d'écriture.
Problèmes étudiés dans ma thèse