La boîte aux lettres avait des dents : propriétés des pièges à facteurs dans le cas bi-infini
Time: 14:00 -- Location: LRI, 445
summary: En 2017, en algorithmique de texte, Prezza a introduit la notion de piège à facteurs :
pour un mot fini w, un piège à facteurs pour w est un ensemble E de positions de w telles que pour tout
facteur f de w, il existe une position de E qui couvre une occurrence de f. Par exemple, pour le mot
"abracadabra", un piège à facteurs est "abracadabra"
(correspondant aux positions 2, 3, 5, 6 et 7) : tout facteur (c'est-à-dire sous-mot contigu) de w a au moins
une occurrence dans w qui recouvre au moins une lettre rouge. Par exemple, "abra" est un facteur de w, et
apparaît au début du mot et est alors couvert par au moins une lettre rouge. La question posée était le calcul
de la taille minimale d'un piège à facteurs.
En 2021, Restivo, Romana et Sciortino, dans le cadre de la combinatoire de mots, ont étendu la notion de piège à
facteurs au cas des mots mono-infinis, c'est-à-dire indexés par N, l'ensemble des entiers naturels. Ils ont montré que les
seuls mots mono-infinis admettant un piège à facteurs fini sont les mots ultimement périodiques. Que se passe-t-il
alors dans le cas des mots bi-infinis, c'est-à-dire les mots indexés par Z, l'ensemble des entiers relatifs ?
Dans cette présentation, je présenterai des résultats surprenants : il existe des mots bi-infinis admettant des
pièges à facteurs finis qui ne sont pas ultimement périodiques. Mieux encore : ce sont des mots (quasi-)Sturmiens !
Je caractériserai les mots admettant des pièges à facteurs finis, et une esquisse de la preuve associée, et en
particulier le lien avec la complexité. Je parlerai enfin de certains pièges à facteurs infinis, par exemple les
pièges de la forme kZ, ainsi que de l'extension des pièges pour les mots vers les pièges pour les shifts.