Outils

Agenda de l'ENS de Lyon

Avoidability of Abelian Repetitions in Words / Évitabilité des répétitions abéliennes dans les mots

Soutenance de thèse

Jeudi 29 juin 2017
10h00
Soutenance de thèse de M. Matthieu ROSENFELD du LIP sous la direction de M. Michaël RAO

Intervenant(s)

Soutenance de thèse de M. Matthieu ROSENFELD du LIP sous la direction de M. Michaël RAO

Description générale
Dans ce document, nous étudions l’évitabilité de différentes formes de répétitions dans les mots. En particulier 3 des 6 chapitres sont dédiés aux répétitions abéliennes en lien notamment à deux questions d’Erdős de 1957 et 1961.
Nous montrons qu’il existe un algorithme décidant, sous certaines conditions, si un mot morphique évite des puissances abéliennes. Cet algorithme élargit la classe sur laquelle les précédents algorithmes pouvaient décider. Une généralisation de cet algorithme nous permet de montrer que les longs carrés abéliens sont évitables sur l’alphabet ternaire et que les carrés additifs sont évitables sur Z². Le premier résultat répond à une questionouverte de Mäkelä datant de 2003 alors que le deuxième rappelle la question ouverte de 1994 concernant l’évitabilité des carrés additifs sur Z.
Une autre généralisation de notre algorithme permet d’étudier l’évitabilité des motifs au sens abélien. Nous montrons que les motifs binaires de longueur supérieure à 14 sont évitables sur l’alphabet binaire, améliorant la précédente borne de 118.
Nous donnons des conditions suffisantes pour qu’un morphisme soit sans longues puissances n-ème k-abéliennes. Ce résultat nous permet de calculer, pour tout k ≥ 3, le nombre minimum de carrés k-abéliens qu’un mot binaire infini doit contenir. Il permet aussi de montrer que les longs carrés 2-abéliens sont évitables sur l’alphabet binaire et qu’il existe un mot ternaire qui ne contient qu’un seul carré 2-abélien en tant que facteur.
Enfin, nous proposons une classification complète des formules binaires en fonction de la taille d’alphabet qu’il faut pour les éviter et du taux de croissance du langage les évitant.
Complément

Amphi B - Site MONOD -ENS de Lyon

Disciplines