Voir la source de Combinatoire des mots

[[Image:Morse-Thue sequence.gif|thumb|right|Construction de la [[suite de Prouhet-Thue-Morse]].]]

La '''combinatoire des mots''' est une branche des [[mathématiques]] et de l'[[informatique théorique]] qui applique l'[[analyse combinatoire]] aux [[mot (mathématiques)|mots]] finis ou infinis.
Cette branche s'est développée à partir de plusieurs branches des mathématiques : la [[théorie des nombres]], la [[théorie des groupes]], les [[probabilités]] et bien sûr la [[combinatoire]]. Elle a des liens avec divers thèmes informatiques, comme l'[[algorithmique du texte]], la [[Algorithme de recherche de sous-chaîne|recherche de motifs]] et la [[compression de données|compression]] de textes.

== Champs d'étude et applications ==

La combinatoire des mots a pour objet d'étude les propriétés de [[mot (mathématiques)|mots finis]] ou [[mot infini|mots infinis]] particuliers. Ceci est à comparer à la théorie des [[langages formels]], qui s'intéresse aux ensembles de mots, en vue de leur représentation et leur analyse.

Pour une classe de mots, l'étude porte sur les caractérisations équivalentes, les propriétés combinatoires, le dénombrement, l'énumération systématique ou la génération aléatoire. On étudie aussi les algorithmes et leur efficacité pour la réalisation effective de ces opérations.

La combinatoire des mots a des applications dans des domaines variés de l'[[informatique théorique]], comme la [[théorie des automates]] et de la [[linguistique]]. Le développement du texte numérique et du [[traitement de texte]] a amené à d'importants développements de la combinatoire des mots. Elle est présente à la base de l'algorithmique du texte, du [[traitement automatique du langage naturel]], du [[traitement de la parole]] et de la [[bio-informatique]].

== Historique ==

La combinatoire des mots remonte aux travaux d'[[Axel Thue]] sur les suites non-répétitives de symboles, au début du {{s-|XX}}. Les principaux travaux, dans les années qui ont suivi, sont ceux de [[Marston Morse]] et de ses coauteurs sur la [[suite de Prouhet-Thue-Morse]] et les [[mot sturmien|mots sturmiens]]. Une célèbre application de la combinatoire des mots est l'usage qui est fait d'une suite sans répétition dans 
la réponse négative à la [[Problème de Burnside|conjecture de Burnside]] apportée par [[Piotr Novikov]] et [[Sergueï I. Adian|Adian]].

C'est [[Marcel-Paul Schützenberger]] qui est le fondateur de la combinatoire des mots moderne, notamment dans des travaux avec [[Roger C. Lyndon]] et [[André Lentin]]. Ses cours ont été rédigés par Jean-François Perrot, et ont donné naissance au livre « Combinatorics on words », ouvrage collectif signé du nom de plume [[M. Lothaire]], et paru en 1983. La combinatoire des mots se développa rapidement à partir de cette date. Deux autres livres de synthèse, signés Lothaire, paraissent ultérieurement, et plusieurs ouvrages collectifs prennent leurs suite.

== Thèmes ==
=== Mots de Lyndon ===
{{article détaillé|mot de Lyndon}}

Les [[mots de Lyndon]], nommés ainsi d'après le mathématicien [[Roger Lyndon]], sont les mots primitifs et minimaux dans leur classe de conjugaison. L'un des résultats de base est que tout mot admet une factorisation décroissante unique en mots de Lyndon (résultat attribué par erreur à Chen, Fox et Lyndon). Un autre résultat remarquable est que le produit, en ordre croissant, des mots de Lyndon dont la longueur divise un entier donné est un mot de [[Nicolaas Govert de Bruijn|de Bruijn]].

=== Répétitions ===
{{article détaillé|mot quasi-périodique|mot sans carré|répétition inévitable|motif inévitable|théorème de Dejean|théorème des répétitions maximales}}

La combinatoire des mots s'est notamment attachée à décrire les conditions dans lesquelles les répétitions apparaissent dans les [[mot (mathématiques)|mots]] ([[mot sans facteur carré|mots sans carré]], entre autres), la construction ou la transformation des mots, par [[morphisme]]. Un cas plus général est couvert par la notion de [[motif inévitable]] ou son contraire, les [[motif évitable|motifs évitables]]. Par exemple le « motif » <math>xyxyx</math> (où <math>x</math> et <math>y</math> sont des symboles) dénote la présence, dans un mot, d'un facteur de la forme <math>uvuvu</math> (où cette fois-ci, <math>u</math> et <math>v</math> sont des mots). Dire qu'un mot ''évite'' ce motif, c'est qu'il ne contient pas ce facteur. Dire qu'un motif est inévitable, c'est affirmer que tout mot assez long contient un facteur de la forme décrite par le motif. Le motif <math>xyx</math> est inévitable, le motif <math>xyxyx</math> est évitable, même sur deux lettres.

La notion de répétition est étendue comme suit aux répétitions fractionnaires : la ''période'' (aussi appelée ''période minimale'') d'un mot <math>w=a_1\cdots a_n</math> est le plus petit entier <math>p</math> tel que <math>a_i=a_{p+i}</math> pour <math>i=1,\ldots,n-p</math>. L{{'}}''exposant'' du mot <math>w</math> est le quotient <math>n/p</math> de sa longueur par sa période. Par exemple, le mot <code>entente</code> a période 3, il est d'exposant 7/3. L'[[exposant critique d'un mot]] infini, qui est le plus grand exposant d'un facteur du mot, dépend de la nature du mot. Un thème similaire est la couverture d'un mot par un motif ; les mots qui admettent une telle couverture sont dits mots [[mot quasi-périodique|quasi-périodiques]].

L'existence d'un seuil pour les répétitions fractionnaires a été [[Conjecture|conjecturé]] par Françoise Dejean en 1972 ; la démonstration de ce fait est le [[théorème de Dejean]].

La notion de répétition est aussi étendue aux répétitions dites abéliennes : ainsi un carré abélien est un mot <math>xy</math> où <math>y</math> est une anagramme de <math>x</math>, c'est-à-dire égal à <math>x</math> à une permutation des lettres près ; par exemple <math>abba</math> est un carré abélien. On peut montrer que des cubes abéliens peuvent être évités sur 3 lettres<ref name="Dekking1979">{{article|nom1=Dekking|prénom1=F.M|titre=Strongly non-repetitive sequences and progression-free sets|journal=Journal of Combinatorial Theory, Series A|volume=27|numéro=2|année=1979|pages=181–185|issn=0097-3165|doi=10.1016/0097-3165(79)90044-X}}</ref>, mais que les carrés abéliens ne sont évitables que sur 4 lettres<ref name="Keränen1992">{{article|nom1=Keränen|prénom1=Veikko|titre=Abelian squares are avoidable on 4 letters|journal=Lecture Notes in Computer Science|volume = 623 : Automata, Languages and Programming. ICALP|année=1992|pages=41–52|issn=0302-9743|doi=10.1007/3-540-55719-9_62}}.</ref>.

Une ''répétition maximale'' (en anglais un ''run'')dans un mot est un facteur d'exposant au moins égal à 2 et qui ne peut être étendue en une répétition plus longue. Le nombre total de répétitions maximales dans un mot de longueur <math>n</math> est au plus égal à <math>n</math>. Ce résultat, appelé le [[théorème des répétitions maximales]], aussi appelé le « théorème des runs » a été démontré en 2015.

=== Mots sans carré et sans puissances ===
{{article détaillé|mot sans carré|carrés distincts dans un mot}}
Un ''carré'' est un mot composé de deux parties égales consécutives, comme « bonbon » ou « papa ». En [[bio-informatique]], un carré est appelé une ''répétition en tandem''. Un mot sans carré est un mot qui ne contient pas de facteur carré. Par exemple, le mot « consécutivement » est un mot sans carré. Plus généralement, un mot sans cube et un mot sans puissance <math>k</math>-ième est un mot qui ne contient pas de cube ou de puissance <math>k</math>-ième en facteur. Il existe des mots infinis sans carré sur tout alphabet d'au moins trois lettres, comme l'a prouvé [[Axel Thue]]. Sur un alphabet à deux lettres, un tel mot n'existe pas. Le [[mot de Prouhet-Thue-Morse]] contient des carrés, en revanche il est sans cube.

Une majoration du nombre de carrés distincts (ou plus généralement de puissances d'un exposant fixe) qui sont facteurs d'un mot donné est un problème posé en 1998 par Fraenkel et Simpson, et a conduit a plusieurs développements sans être entièrement résolu<ref>{{Article
|auteur1= Aviezri S. Fraenkel | auteur2 = Jamie Simpson 
|titre= How many squares can a string contain?
|périodique= [[J. Comb. Theory]], Sér. A
|volume= 82
|numéro=1
|date=1998
|pages= 112-120
|zbl= 0910.05001
}}.</ref>{{,}}<ref>{{Article
|auteur1= Shuo Li
|titre= On the number of k-powers in a finite word
|périodique= [[Advances in Applied Mathematics]]
|volume= 139
|numéro article = 102371
|date= août 2022
|doi= 10.1016/j.aam.2022.102371
|arxiv= 2203.16742}}.</ref>.

=== Complexité combinatoire d'un mot ===
[[Image:Fibonacci word cutting sequence.png|thumb|Le [[mot de Fibonacci]], caractérisé par une droite de pente <math>\varphi</math> ou <math>\varphi-1</math> avec <math>\varphi</math>, le [[nombre d'or]]]]
Il existe plusieurs manières de cerner la ''complexité'' d'une suite infinie de symboles. Intuitivement, ces notions doivent indiquer à quel point une suite est « compliquée » ou « complexe », ou « aléatoire », ou « chaotique ». La [[théorie de la complexité des algorithmes|complexité algorithmique]] est une mesure qui évalue combien elle est difficile à construire. Cette difficulté est mesurée par la taille du programme nécessaire pour la construire, ou par temps qu’il faut pour calculer son  ''n''-ième terme. La [[théorie algorithmique de l'information]] fondée par [[Kolmogorov]], [[Solomonoff]] et [[Chaitin]]   aborde ces problèmes. La [[complexité de Kolmogorov]] d’une suite est la taille du plus court programme sur une [[machine de Turing]] qui engendre cette suite. La notion est relié aussi à la compressibilité d’une séquence.

Une autre mesure, plus arithmétique ou combinatoire, est la complexité « en facteurs », en anglais {{Citation étrangère|langue=en|subword complexity}}, appelé aussi '''complexité combinatoire'''. Elle mesure le nombre de facteurs qu'un mot possède pour chaque longueur. Formellement, 
la ''fonction de complexité'' d'un mot fini ou infini <math>x</math> est la fonction <math>n\mapsto c_x(n)</math> qui, pour chaque entier <math>n</math>, compte le nombre de facteurs <math>c_x(n)</math>(ou blocs) de longueur <math>n</math> dans ce mot.
Pour un mot infini <math>x</math>, un résultat dû à Ethan M. Coven et [[Gustav Hedlund]] dit que si <math>c_x(n)\le n</math> pour un entier <math>n</math>, alors le mot <math>x</math> est ultimement périodique. Les mots infinis apériodiques de complexité minimale ont donc une fonction de complexité égale à <math>n+1</math>. Ce sont les [[mot sturmien|mots sturmiens]].
Le plus connu des mots sturmiens est le [[mot de Fibonacci]]. Des mesures voisines sont la [[complexité d'un mot|complexité palindromique]] qui mesure le nombre de palindromes, ou la [[complexité d'un mot|complexité arithmétique]].

Le terme de « complexité combinatoire », en opposition à la complexité algorithmique, est assez récent : on le trouve par exemple chez  Jean-Paul Allouche<ref name="Allouche" /> ou Michel Rigo<ref name="Rigo1" />.

{{article détaillé|complexité combinatoire d'un mot}}

=== Mots automatiques ===
{{article détaillé|suite automatique}}
Les ''mots automatiques'' sont des suites que l'on peut définir à l'aide d'[[automate fini|automates finis]].
La [[suite de Prouhet-Thue-Morse]] est l'exemple paradigmatique de cette famille. Les [[suite de pliage de papier|pliages de papiers]] en sont un autre exemple.

=== Mots morphiques ===
{{article détaillé|mot morphique|conjecture de Billaud}}
Un ''mot morphique'' est un mot infini obtenu par [[itération]] d'un morphisme, suivi de l'application d'un deuxième morphisme. En absence du deuxième morphisme, on parle de ''mot purement morphique''. C'est une méthode très efficace et répandue de construction de mots infinie. Elle est « robuste » en ce sens qu'elle est stable par toute sorte d'opérations. Par exemple, le [[mot de Fibonacci]] infini est un mot purement morphique, la [[suite de Prouhet-Thue-Morse]] également. La suite caractéristique des carrés : {{indente | 11001000010000001000...}} est morphique, mais n'est pas purement morphique.

La ''conjecture de Billaud'' est une conjecture sur la possibilité de caractériser un mot fini par certains de ses sous-mots.

=== Mots de Toeplitz et de Stewart ===
{{article détaillé|mot de Toeplitz}}
Un ''mot de Toeplitz'' est un mot infini obtenu par un processus itératif qui est décrit par une suite d'une ou plusieurs règles d'interclassement dits « motifs de Toeplitz ». Les plus connues de ces mots sont la suite des [[suite de pliage de papier]] et la suite chorale de Stewart.

=== Complexité abélienne ===
{{article détaillé|complexité abélienne d'un mot}}
La '''complexité abélienne''' d'un [[mot (mathématiques)|mot]] fini ou [[mot infini|infini]] est la fonction qui compte le nombre de [[mot (mathématiques)|facteurs]] de longueur donnée dans ce mot, à permutation de lettres près. C'est une autre mesure de la ''complexité combinatoire'' d'une suite.

=== Équations entre mots ===
{{article détaillé|Équation entre mots}}
Une '''équation de mots''' ou une '''équation entre mots''' (en anglais ''word equation'') est un couple <math>(U,V)</math> de [[mot (mathématiques)|mot]]s, usuellement écrit sous la forme d'une équation 
:<math>U=V</math>.
Ici, <math>U</math> et <math>V</math> sont des mots composés lettres qui sont des constantes ou des variables. Les constantes sont écrits en minuscules, les variables en majuscules. Par exemple, l'équation
:<math>abXbX=XbXba</math>
contient quatre occurrences de la variable <math>X</math>, et des constantes <math>a</math> et <math>b</math>. Une ''solution'' d'une équation est un ensemble de mots sans variables, un pour chaque variable, tel que la substitution des mots aux variables rend les deux composantes de l’équation identiques. Par exemple, pour <math>X=a</math> (et plus généralement pour <math>X=(ab)^ka</math> avec <math>k\ge0</math>, les deux côtés de l'équation deviennent égaux, à <math>ababa</math> (et plus généralement à <math>(ab)^{2k+2}a</math>).

Un célèbre théorème de Makanin<ref name="Mak77">{{harvsp|Makanin|1977|id=M77}}.</ref>{{,}}<ref name= "Die02">{{harvsp|Diekert|2002|p=}}.</ref> dit qu'il est décidable si une équation de mots, et plus généralement un ensemble d'équations de mots, possède une solution. En cela, les équations de mots se distinguent des [[Équation diophantienne|équations diophantiennes]] pour lesquels l'existence de solutions est indécidable par le théorème de [[Youri Matiiassevitch |Matiiassevitch]] résolvant le [[dixième problème de Hilbert]].

Un problème lié est la description de toutes les solutions d'une équation donnée, sous forme paramétrée en général. La première étude systématique dans cette direction est faite par Hmelevskii<ref>{{harvsp|Hmelevskii|1976|p=}}.</ref>.

== Récurrence ==
Un mot infini <math>x</math> est '''récurrent''' si tout facteur de <math>x</math> apparaît une infinité de fois dans <math>x</math>.
* Le mot <math>ab^\omega</math> n'est pas récurrent.
* Le [[Constante de Champernowne|mot de Champernowne]] binaire {{indente|<math>0100011011000001010011\ldots </math>}} formé de la concaténation des développements binaires des [[Entier naturel|entiers naturels]] est récurrent.
* Un mot ultimement périodique et récurrent est périodique.
Un mot infini <math>x</math> est '''uniformément récurrent''' ou '''à lacunes bornées''' si deux occurrences consécutives d'un facteur de <math>x</math> sont à distance bornée. Plus précisément, pour tout facteur <math>u</math> de <math>x</math>, il existe une constante <math>N(u)</math> telle que deux occurrences consécutives de <math>u</math> dans <math>x</math> sont à distance au plus <math>N(u)</math>.
* Le mot de Champernowne binaire n'est pas uniformément récurrent. En effet, deux occurrences consécutives du symbole <math>1</math> peuvent être séparées par des séquences arbitrairement longues de <math>0</math>.
* Le [[mot de Fibonacci]] {{indente|<math>01001010 01001 01001010\ldots </math>}} est uniformément récurrent. Par exemple, les occurrences du chiffre <math>1</math> dans ce mot infini sont les éléments de la {{OEIS|id=A001950}}, soit 2, 5, 7, 10, 13, 15, 18,... La distance entre deux <math>1</math> consécutifs est donc au plus 3.
* Le [[suite de Prouhet-Thue-Morse|mot de Thue-Morse]] est uniformément récurrent.
Il y a un lien entre les mots uniformément récurrents et les [[ensemble syndétique|ensembles syndétiques]].
Un ensemble <math>S</math> d'entiers naturels est appelé '''syndétique''' s'il existe un entier <math>N</math> tel que pour deux entiers consécutifs <math>s<t</math> de <math>S</math>, on ait <math>t-s<N</math>. Un mot infini <math>x</math> est donc uniformément récurrent si, pour tout facteur <math>u</math> de <math>x</math>, l'ensemble <math>S(u)</math> des débuts d'occurrence de <math>u</math> dans <math>x</math> est syndétique.

La '''fonction de récurrence''' <math>R</math> d'un mot infini <math>x</math> donne la valeur maximale des lacunes entre occurrences consécutives de mots d'une longueur donnée. Plus précisément, <math>R(n)</math> est le plus petit entier <math>N</math> tel que tout facteur de <math>x</math> de longueur <math>n</math> soit facteur de tout facteur de longueur <math>N</math> de <math>x</math>, formellement {{indente|<math>R(n)=\inf\{N\mid \forall w\in F_N(x), F_n(w)=F_n(x)\}</math>}}
On peut voir l'entier <math>R(n)</math> comme la largeur minimale d'une fenêtre que l'on glisse sur le mot <math>x</math> et qui a la propriété que tout facteur de longueur <math>n</math> figure toujours dans la section couverte par la fenêtre.
* Pour le mot de Fibonacci, on a <math>R(1)=3</math>, et <math>R(2)=6</math>; en effet, le facteur <math>01010</math> du mot de Fibonacci ne contient pas le facteur <math>00</math>, mais tout facteur de longueur 6 contient les trois facteurs <math>00,01,10</math> parce que <math>10101</math> n'est pas facteur du mot de Fibonacci.
=== Fonction de récurrence de la suite de Prouhet-Thue-Morse ===
Pour le [[suite de Prouhet-Thue-Morse|mot de Thue-Morse]] <math>01101001100101101001\ldots</math>, on a <math>R(1)=3</math> (tout facteur de longueur 3 contient un <math>0</math> et un <math>1</math>) et <math>R(2)=9</math> (le facteur <math>01011010</math> ne contient pas <math>11</math>). En fait, la fonction de récurrence a été calculée par Morse et Hedlund, dès 1938<ref>Allouche & Shallit (2003), pages 328-331, et Morse & Hedlund (1938), pages 834-839.</ref>. Les premières valeurs sont données dans la table suivante : 
{| class="wikitable centre" width="50%" align="center"
|+ Fonction de récurrence de la suite de Prouhet-Thue-Morse
! <math>n</math>
! 1 !! 2!! 3!! 4!! 5!! 6!! 7!! 8!! 9!! 10
|----- 
|align="center"| <math>R(n)</math>||align="center"| 3
|align="center"| 9||align="center"| 11
|align="center"| 21||align="center"| 22
|align="center"| 41||align="center"| 42
|align="center"| 43||align="center"| 44
|align="center"| 81
|}
C'est la {{OEIS|id=A179867}}. La formule de récurrence est toute simple : pour <math>n\ge2</math>, on a {{indente|<math>R(2n)=2R(n+1)-1</math>}} {{indente|<math>R(2n+1)=2R(n+1)</math>.}}
Il en résulte la forme close suivante. Posons <math>n=2^r+p</math>, avec <math>2\le p \le 2^r+1</math>. Une telle écriture est toujours possible pour <math>n\ge3</math>. Alors {{indente|<math>R(n)= 10 \cdot 2^r+p-1</math>.}}

=== Fonction de récurrence du mot infini de Fibonacci ===
Cette fonction de récurrence a une expression un peu moins simple, et elle est connue depuis l'article de Morse et Hedlund de 1940. On a {{indente|<math>R(n)=F_{N+1}+F_N+n-1</math>}} où <math>N</math> est l'entier tel que <math>F_N \le n < F_{N+1}</math>. Ici, les <math>F_N</math> sont les nombres de Fibonacci avec <math>F_0=0, F_1=1</math>.
{| class="wikitable centre" width="50%" align="center"
|+ Fonction de récurrence du mot infini de Fibonacci
! <math>n</math>
! 1 !! 2!! 3!! 4!! 5!! 6!! 7!! 8!! 9!! 10
|----- 
|align="center"| <math>R(n)</math>||align="center"| 3
|align="center"| 6||align="center"| 10
|align="center"| 11||align="center"| 17
|align="center"| 18||align="center"| 19
|align="center"| 28||align="center"| 29
|align="center"| 30
|}
C'est la {{OEIS|id=A183545}}. Cette formule s'étend à tous les [[mot sturmien|mots sturmiens]].

== Notes et références ==
{{Traduction/Référence|en|Combinatorics on words|384739852|type=note}}
{{Références|références=
<ref name="Allouche">{{article|auteur=Jean-Paul Allouche|titre=Surveying some notions of complexity for finite and infinite sequences| pages =27-37 |lieu=Kyoto|éditeur=Res. Inst. Math. Sci. (RIMS) | math reviews= MR3014836 | périodique = RIMS Kôkyûroku Bessatsu, B34 : Functions in number theory and their probabilistic aspects|année = 2012| url = http://repository.kulib.kyoto-u.ac.jp/dspace/bitstream/2433/198090/1/B34-02.pdf}}.
</ref>
<ref name="Rigo1">{{Ouvrage | auteur1=Michel Rigo | titre=Formal Languages, Automata and Numeration Systems | volume=1 | éditeur=John Wiley & Sons | année=2014 | pages totales=336 | isbn=978-1-84821-615-0 | isbn2=1848216157}}.</ref>
}}

== Voir aussi ==

=== Articles connexes ===
*[[Métrique des mots]]
* [[Problème du mot]]
* [[Théorème de périodicité de Fine et Wilf]]
* [[Congruence de Simon]]

=== Bibliographie ===
<!-- Histoire -->
;Histoire
* {{Article| prénom1 = Jean|nom1= Berstel|prénom2=Dominique|nom2= Perrin
| titre = The origins of combinatorics on words| journal = European Journal of Combinatorics
| année = 2007|volume=28
| pages= 996–1022|url= http://www-igm.univ-mlv.fr/%7Eberstel/Articles/2007Origins.pdf}}.
* {{Article|prénom1=Dominique|nom1= Perrin
| titre = Les débuts de la combinatoire des mots| journal = séminaire EHESS
| année = 2005|url= http://www-igm.univ-mlv.fr/~perrin/Recherche/Seminaires/EHESS/TransBeginnings.pdf}}.
;Articles de synthèse
* {{Ouvrage | auteur1=Klaus Ulrich Schulz | responsabilité1=éditeur | titre=Word equations and related topics | éditeur=Springer-Verlag | année=1992 | pages totales=256 | isbn=978-3-540-55124-9 | lire en ligne=https://books.google.com/books?id=z-mixu2SLyoC&printsec=frontcover | libellé=1992}} — Actes du colloque IWWERT '90, Tübingen, Allemagne, 1-{{date-|3 octobre 1990}}
* {{chapitre| libellé = 1997
 | auteur1 = Christian Choffrut| auteur2 = Juhani Karhumäki
 | titre chapitre = Combinatorics of words| auteurs ouvrage = G. Rozenberg, A. Salomaa (éditeurs)
 | titre ouvrage = Handbook of Formal Languages| éditeur = Springer Verlag
 | année = 1997| volume = 1| titre volume = Word, Language, Grammar
 | passage  = 329-438| isbn = 978-3-540-60420-4| id = CK
 | présentation en ligne = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.54.3135&rep=rep1&type=pdf}}
* {{chapitre| libellé = 2002
 |auteur = Volker Diekert | titre chapitre = Makanin's Algorithm | numéro chapitre = 12 
 |auteur ouvrage = M. Lothaire 
 | titre ouvrage = Algebraic Combinatorics on Words | collection = Encyclopedia of Mathematics and its Applications
 | numéro dans collection = 90 | éditeur =  Cambridge University Press | année = 2002 | isbn =  | passage = 387–442}}.
* {{Article| libellé = 2003
 | prénom1 = Jean|nom1= Berstel|prénom2=Juhani|nom2= Karhumäki
 | titre = Combinatorics on words - a tutorial| journal = Bull. Eur. Assoc. Theor. Comput. Sci. (EATCS)
 | année = 2003|volume=79
 | pages= 178-228|url= http://www-igm.univ-mlv.fr/~berstel/Articles/2003TutorialCoWdec03.pdf}}.
* {{Article| libellé = 2004
 |prénom1=Juhani|nom1= Karhumäki
 | titre = Combinatorics on words: a new challenging topic| journal = TUCS Technical Report
 | année=2004|numéro=645
 | url= http://www.tucs.fi/publications/attachment.php?fname=TR645.pdf}}.
* {{chapitre| libellé = 2015
| auteur1 = Dominique Perrin| auteur2 = [[Antonio Restivo]]
| titre chapitre = Words| auteurs ouvrage = Miklos Bona (éditeur)
| titre ouvrage = Handbook of Enumerative Combinatorics| éditeur = Chapman and Hall/CRC
| année = 2015
| isbn = 9781482220865| pages totales = 1086
| présentation en ligne = https://cel.archives-ouvertes.fr/LIGM_MOA/hal-01121901
| lire en ligne = http://www-igm.univ-mlv.fr/~perrin/Recherche/Publications/BookChapters/enhandbook.pdf
}}

;Lothaire
* {{Ouvrage | prénom1=M. | nom1=Lothaire | titre=Combinatorics on words | éditeur=Cambridge University Press | collection=Cambridge Mathematical Library | année=1997 | pages totales=xviii+238 | isbn=978-0-521-59924-5 | doi=10.1017/CBO9780511566097 | math reviews=1475463 | présentation en ligne=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511566097}}
* {{Ouvrage | prénom1=M. | nom1=Lothaire | titre=Algebraic combinatorics on words | éditeur=[[Cambridge University Press]] | collection=Encyclopedia of Mathematics and its Applications | numéro dans collection=90 | année=2002 | pages totales=504 | isbn=978-0-521-81220-7 | présentation en ligne=http://www-igm.univ-mlv.fr/~berstel/Lothaire/AlgCWContents.html}} 
* {{Ouvrage | langue=en | prénom1=M. | nom1=Lothaire | titre=Applied combinatorics on words | éditeur=[[Cambridge University Press]] | collection=Encyclopedia of Mathematics and its Applications | lieu=Cambridge (GB) | numéro dans collection=105 | année=2005 | pages totales=610 | isbn=978-0-521-84802-2 | présentation en ligne=http://www-igm.univ-mlv.fr/~berstel/Lothaire/AppliedCW/AppCWContents.html}}
;Berthé — Rigo
* {{Ouvrage | auteur1=Valérie Berthé | auteur2=Michel Rigo | responsabilité2=éditeurs | titre=Sequences, groups, and number theory | éditeur=Birkhäuser | collection=Trends in Mathematics | année=2018 | pages totales=xxvi+576 | isbn=978-3-319-69151-0}}
* {{Ouvrage
 | auteur1=Valérie Berthé
 | auteur2=Michel Rigo
 | responsabilité2=éditeurs
 | titre=Combinatorics, words and symbolic dynamics
 | éditeur=Cambridge University Press
 | collection=Encyclopedia of Mathematics and its Applications
 | lieu=Cambridge, Royaume Uni
 | numéro dans collection=159
 | année=2016
 | mois=mars
 | pages totales=496
 | isbn=978-1-107-07702-7
}}
* {{Ouvrage | auteur1=[[Valérie Berthé]] | auteur2=Michel Rigo | responsabilité2=éditeurs | titre=Combinatorics, automata and number theory | éditeur=Cambridge University Press | collection=Encyclopedia of Mathematics and its Applications | numéro dans collection=135 | année=2010 | pages totales=615 | isbn=978-0-521-51597-9 | lire en ligne=https://books.google.com/books?id=gTEOscYGYG4C&printsec=frontcover}}
;Monographies <!-- par ordre alphabétique -->
* {{Ouvrage | langue=en | prénom1=Jean-Paul | nom1=Allouche | lien auteur1=Jean-Paul Allouche | prénom2=Jeffrey O. | nom2=Shallit | titre=Automatic sequences | sous-titre=Theory, applications, generalizations | éditeur=Cambridge University Press | lieu=Cambridge | année=2003 | pages totales=571 | isbn=0-521-82332-3 | math reviews=1997038 | zbl=1086.11015}}
* {{Ouvrage | prénom1=Jean | nom1=Berstel | prénom2=Aaron | nom2=Lauve | prénom3=Christophe | nom3=Reutenauer | prénom4=Franco V. | nom4=Saliola | titre=Combinatorics on words : Christoffel words and repetitions in words | éditeur=[[American Mathematical Society]] et [[Centre de recherches mathématiques]] | année=2008 | pages totales=504 | isbn=978-1-4200-7267-9}}
* {{Ouvrage
 | auteur1=[[Maxime Crochemore]]
 | auteur2=Wojciech Rytter
 | titre=Jewels of stringology
 | sous-titre=Text Algorithms
 | éditeur=World Scientific Publishing
 | année=2002
 | pages totales=310
 | isbn=978-981-02-4897-0
 | lire en ligne=https://books.google.com/books?id=9NdohJXtIyYC&printsec=frontcover
 | id=Jewels
}}
* {{ouvrage
| auteur1=Maxime Crochemore 
| auteur2 =  Thierry Lecroq
| auteur3 =  Wojciech Rytter
| titre = 125 Problems in Text Algorithms with Solutions 
| éditeur = Cambridge University Press
| pages totales = 345
| isbn  =  978-1-108-83583-1
| isbn2= 978-1-108-79885-3 
| date = 2021
}}
* {{Ouvrage | auteur1=Christophe Reutenauer | titre=From Christoffel Words to Markoff Numbers | éditeur=Oxford University Press | année=2019 | pages totales=156 | isbn=978-0-19-882754-2 | lire en ligne=https://books.google.com/books?id=79t1DwAAQBAJ&printsec=frontcover}}.
;Textes historiques
* {{Ouvrage|auteur1=Ju. I. Hmelevskii|titre=Equations in free semigroups|éditeur=American Mathematical Society, Proceedings of the Steklov Institute of Mathematics 107 (1971)|année=1976|pages totales=270|isbn=978-0-8218-3007-9|math reviews=0393284|zbl=0326.02032|présentation en ligne=http://www.ams.org/bookstore-getitem/item=STEKLO-107}} {{commentaire biblio SRL|Traduit de l’original russe, paru en 1971, par G. A. Kandall}}.

* {{article | auteur = Gennadiy S. Makanine | titre = The problem of solvability of equations in a free semigroup | journal = Math. Sbornik (N.S.)  | année = 1977 | volume = 103 | numéro = 2 | pages = 147-236, 319| math reviews = 0470107 | id=M77}} — Article complet, en russe. Traduction anglaise : Math. USSR Sbornik 32 (1977)
 
{{portail|mathématiques | informatique théorique}}

[[Catégorie:Combinatoire des mots|*]]