29-31 mai 2024 Orléans (France)
String attractors sur N et Z : facteurs, attrapez-les tous !
Pierre Béaur  1@  
1 : Graphes, Algorithmes et Combinatoire - LISN
Université Paris-Saclay,Sorbonne Universités

Un piège à facteurs (en anglais string attractor) d'un mot est un ensemble de positions permettant de capturer l'ensemble des facteurs d'un mot. Par exemple, tout facteur du mot abracadra a au moins une occurrence recouvrant l'une des positions 1, 2, 3, 4 ou 6 (correspondant aux positions soulignées dans abracadabra) : on dit que {1,2,3,4,6} capture tous les facteurs, et est un piège à facteurs de abracadabra. Cet objet combinatoire a originellement été créé pour les mots finis, mais il est aussi possible de l'étendre aux mots infinis. Dans cette présentation, je présenterai le cas des mots mono-infinis, càd indexés par N, traité par Restivo, Romana et Sciortino en 2023 ; puis j'expliquerai l'extension au cas des mots bi-infinis, càd indexés par Z. En particulier, je ferai le lien entre existence d'un piège à facteurs fini et complexité d'un mot bi-infini. Les travaux présentés résultent d'une collaboration avec France Gheeraert et Benjamin Hellouin.


Personnes connectées : 2 Vie privée | Accessibilité
Chargement...