Motifs évitables et régularités dans les mots

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

Titre

Résumé, Abstract

Remerciements

Introduction

Chapitre 1 : Mots et motifs

1. Définitions usuelles
2. Motifs
3. Évitabilité
4. Premières propriétés
5. Motifs avec constantes, formules
6. Variantes
7. Évitabilité sur un alphabet non fixé
8. Motifs verrouillés

Chapitre 2 : Classification des motifs binaires

1. Motifs inévitables
2. Motifs 2-inévitables
3. 3-évitabilité
4. 2-évitabilité : les résultats de Peter Roth
5. Le cas de AABBA
6. Autres preuves de 2-évitabilité
7. Classification des motifs binaires

Chapitre 3 : DOL-évitabilité, HDOL-évitabilité

1. DOL-langages et HDOL-langages
2. Motifs DOL-évitables et HDOL-évitables
3. Quelques résultats faciles
4. Réduction des DOL et HDOL
5. Preuves de DOL-inévitabilité
6. Nouvelle classification des motifs binaires

Chapitre 4 : Finitude de l'ensemble des motifs n-aires k-inévitables pour k>1

1. Introduction : l(n,k)
2. Les grands motifs n-aires sont 2-DOL-évitables
3. Une meilleure borne avec des HDOL-systèmes
4. Valeurs connues de l(n,k)

Chapitre 5 : Dénombrement des mots évitant un motif : le cas des chevauchements

1. Introduction
2. Résultats antérieurs
3. Une bijection entre le langage des mots binaires sans chevauchement et un langage rationnel
4. Des matrices pour calculer u(n)
5. Étude asymptotique de la suite (u(n))
6. Avec d'autres motifs

Chapitre 6 : Un algorithme pour décider si un HDOL-langage évite un motif

1. Morphismes circulaires
2. L'image inverse d'un motif par un morphisme circulaire
3. L'algorithme
4. Cas des morphismes non expansifs
5. Conclusion
6. Exemple

Chapitre 7 : Une autre application des morphismes circulaires : calculs de complexités de suites

1. Introduction
2. Suites ou langages ?
3. Facteurs spéciaux et bispéciaux
4. Action d'un morphisme circulaire
5. Application : suites de complexité affine
6. Quelques exemples de calculs de complexité de suites définies par morphisme

Conclusion

Annexe A : Classification partielle des motifs ternaires

Contenant le dictionnaire des motifs ternaires

(pages 126 à 159) PS

Bibliographie

Notations

Index

Liste des tables et figures

Table des matières