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.
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