Accès direct au contenu

 

logo du site ENS

Logo du site Ens Lyon

Recherche

Accueil  >  ENS de Lyon > Recherche > Soutenances de thèses > Thèses en sc. exactes et exp.

Imprimer

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

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

Lieu(x) :

Site Monod - 46 allée d'Italie
Amphi B - Site MONOD -ENS de Lyon
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.

Retour au haut de la page

Pôle Recherche
 
 
Mise à jour le 8 juin 2017
Ens de Lyon
15 parvis René Descartes - BP 7000 69342 Lyon Cedex 07 - FRANCE
Tél. : Site René Descartes (siège) : +33 (0) 4 37 37 60 00 / Site Jacques Monod : +33 (0) 4 72 72 80 00