Motifs évitables et régularités dans les mots
Ceci est en principe la version définitive (28 juin 1994) de ma thèse.
Si vous y trouvez des erreurs (il y en a certainement),
que ce soit d'orthographe, de typo ou de maths, prévenez-moi.
Si vous voulez un exemplaire
papier, il suffit de me le demander en indiquant votre adresse postale.
Si vous êtes vraiment pressé, vous pouvez imprimer le
fichier PostScript complet (compressé),
ou seulement le chapitre qui vous intéresse.
Si vous êtes curieux et courageux, vous pouvez même regarder les
sources en TeX (archive tar compressée).
(page 1)
PS
(page 2)
PS
(page 3)
PS
(pages 5 à 8)
PS
Chapitre 1 : Mots et motifs
(pages 9 à 27)
PS
- Définitions usuelles
- Motifs
- Évitabilité
- Premières propriétés
- Motifs avec constantes, formules
- Variantes
- Évitabilité sur un alphabet non fixé
- Motifs verrouillés
Chapitre 2 : Classification des motifs binaires
(pages 29 à 42)
PS
- Motifs inévitables
- Motifs 2-inévitables
- 3-évitabilité
- 2-évitabilité : les résultats de Peter Roth
- Le cas de AABBA
- Autres preuves de 2-évitabilité
- Classification des motifs binaires
Chapitre 3 : DOL-évitabilité, HDOL-évitabilité
(pages 43 à 62)
PS
- DOL-langages et HDOL-langages
- Motifs DOL-évitables et HDOL-évitables
- Quelques résultats faciles
- Réduction des DOL et HDOL
- Preuves de DOL-inévitabilité
- Nouvelle classification des motifs binaires
Chapitre 4 : Finitude de l'ensemble des motifs n-aires k-inévitables
pour k>1
(pages 63 à 70)
PS
- Introduction : l(n,k)
- Les grands motifs n-aires sont 2-DOL-évitables
- Une meilleure borne avec des HDOL-systèmes
- Valeurs connues de l(n,k)
Chapitre 5 : Dénombrement des mots évitant un motif :
le cas des chevauchements
(pages 71 à 87)
PS
- Introduction
- Résultats antérieurs
- Une bijection entre le langage des mots binaires
sans chevauchement et un langage rationnel
- Des matrices pour calculer u(n)
- Étude asymptotique de la suite (u(n))
- Avec d'autres motifs
Chapitre 6 : Un algorithme pour décider si un HDOL-langage
évite un motif
(pages 89 à 104)
PS
- Morphismes circulaires
- L'image inverse d'un motif par un morphisme circulaire
- L'algorithme
- Cas des morphismes non expansifs
- Conclusion
- Exemple
Chapitre 7 : Une autre application des morphismes circulaires :
calculs de complexités de suites
(pages 105 à 118)
PS
- Introduction
- Suites ou langages ?
- Facteurs spéciaux et bispéciaux
- Action d'un morphisme circulaire
- Application : suites de complexité affine
- Quelques exemples de calculs de complexité de suites définies
par morphisme
(pages 119 à 120)
PS
Annexe A : Classification partielle des motifs ternaires
(pages 121 à 125)
PS
Contenant le dictionnaire des motifs ternaires
(pages 126 à 159)
PS
Bibliographie
(pages 161 à 165)
PS
Notations
(pages 167 à 168)
PS
Index
(pages 169 à 176)
PS
Liste des tables et figures
(page 177)
PS
Table des matières
(pages 179 à 181)
PS
JC 1994-12-19