Séminaire Algorithmique : France Gheeraert (LAMFA, Univ. Picardie) «String attractors, ou comment capturer la combinatoire d’un texte»

Les string attractors sont des objets combinatoires introduits par Kempa et Prezza dans le but d’unifier différentes mesures de compressibilité de texte provenant de techniques classiques telles que LZ77 ou la transformée de Burrows-Wheeler. Etant donné un texte, un string attractor est un ensemble de positions permettant de capturer tous les motifs apparaissant dans ce texte. La recherche d’un tel ensemble de positions est un problème NP-complet. Pour contourner cette difficulté, les recherches se sont rapidement tournées vers des textes possédant des propriétés combinatoires particulières.

Dans cet exposé, je présenterai les string attractors et les résultats classiques à leur sujet. J’aborderai ensuite le cas particulier des préfixes de la suite (symbolique) de Fibonacci comme une première étape vers l’étude d’autres textes bien connus en combinatoire des mots.