Utilisateur:ManiacParisien/Lexique de combinatoire des mots

Lexique de combinatoire des mots

Sommaire :

• Haut – A
• B
• C
• D
• E
• F
• G
• H
• I
• J
• K
• L
• M
• N
• O
• P
• Q
• R
• S
• T
• U
• V
• W
• X
• Y
• Z

A

• alphabet : réservoir de symboles, aussi appelés lettres, dont les suites constituent des mots
• morphisme alphabétique, aussi appelé morphisme décroissant : un morphisme qui envoie une lettre sur une lettre ou le mot vide.
• anti-puissance', une anti-puissance d'ordre k est une concaténation de k blocs consécutifs de même longueur distincts deux-à-deux. Tout mot infini contient des puissance ou des anti-puissances de tout ordre.

B

• bord d'un mot : c'est un mot qui est à la fois préfixe et suffixe. Par exemple, aba est un bord de ababa. Le mot vide compte comme bord, le mot tout entier non.

C

• conjugué : un mot est conjugué d'un autre s'il s'en par une permutation circulaire. Par exemple, cdeab est un conjugué de abcde. Un mot est primitif si et seulement s'il est différent de tous ses conjugués.
• mot circulaire : un mot circulaire est un mot écrit sur un cercle; c'est aussi l'ensemble de conjugués d'un mot. On doit aussi classe de conjugaison ou collier.
• collier : synonyme de mot circulaire
• carré : c'est un mot des la forme xx, pour x non vide
• mot sans carré : un mot dont aucun facteur est un carré
• morphisme sans carré : un morphisme qui préserve les mots sans carré, c'est-à-dire tel que l’image d'un mot sans carré est un mot sans carré.
• complexité cyclique : compte le nombre de classes de conjugaison des facteurs de longueur $n$ d'un mot infini $x$.

D

• une suite (i. e. un mot infini) est disjonctive si elle contient tous les mots en facteurs. La suite d'Ehrenfeucht-Mycielski est disjonctive.

E

• exposant : si $x=y^{p/q}$, le nombre $p/q$ est l'exposant de y. Par exemple, 5/2 est l'exposant de ab dans $ababa=(ab)^{5/2}$.
• morphisme élémentaire : un morphisme qui n'est pas simplifiable. Un morphisme élémentaire est injectif sur des mots finis et infinis; il est non effaçant.

F

• facteur : un facteur d'un mot est une bloc de lettres consécutives du mot. Par exemple, $aa$ est un facteur de $abaab$.
• facteur interne : un facteur qui apparaît précédé et suivi d'un mot non vide. Par exemple, $aa$ est facteur interne de $abaab$.
• mot fermé : synonyme de mot de retour complet : un mot qui possède un bord qui n’apparaît pas en facteur interne. Par exemple, $ababa$ est fermé. Le bord en question est toujours le plus grand bord.

I

• morphisme infixe : un morphisme tel que l'image d'aucune lettre n'est facteur de l'image d'une autre lettre. Un morphisme infixe est injectif sur l'alphabet.

L

• lettre : constituant d'un alphabet
• longueur d'un mot : nombre de symboles formant le mot; la longueur d'un mot w est notée |w|.
• mot de Lyndon : un mot qui est strictement plus petit que ses conjugués. Il y a un mot de Lyndon unique dans chaque classe de conjugaison d'un mot primitif
• morphisme littéral : un morphisme qui envoie une lettre sur une lettre, aussi appelé morphisme lettre à lettre ou morphisme préservant la longueur (length-preserving)

M

• mot : suite de lettres
• mot vide : l'unique mot de longueur 0, composé d'aucun mot, noté ε (epsilon)
• image miroir : l'image miroir de $a_{1}\cdots a_{n}$ est $a_{n}\cdots a_{1}$. Est noté $w^{\sim }$ ou ${\tilde {w}}$ ou $w^{R}$. Se dit aussi retourné (reversal en anglais)
• morphisme : une fonction telle que l'image d'un produit de mots est le produit des images.

O

• mot ouvert : un mot qui n'est pas fermé.

P

• palindrome : un mot qui est inchangé si on le lit de gauche à droite ou de droite à gauche. C'est un mot égal à son image miroir.
• puissance : un mot x de la forme y^k, pour k entier (puissance entière, en opposition à puissance rationnelle)
• puissance rationnelle : un mot x de la forme $y^{k}z$, où z est un préfixe de y de longueur p. Si y est de longueur q, la longueur de x est $|x|=kq+p$; le rapport $|x|/|y|=k+p/q$ est l'exposant de x comme puissance de y ; c'est un nombre rationnel. Par exemple, ababa est une puissance 5/2 de ab.
• mot primitif : un mot est primitif s'il n'est pas puissance entière d'un autre mot, donc si $x=y^{n}$ avec $n$ entier implique $n=1$.
• période: un entier p est une période du mot $w=a_{1}\cdots a_{n}$ si $a_{i}=a_{i+p}$ pour $i=1,\ldots n-p$. Dans ce cas, w est une puissance (rationnelle) de $x=a_{1}\cdots a_{p}$. L'exposant de cette puissance est $n/p$. Ainsi, l'entier 5 est une période de abaababa, et $abaababa=(abaab)^{8/5}$.
• mot préfixe normal : un mot binaire w (sur 0,1) est préfixe normal si, pour tout entier k, le préfixe de longueur k de w contient plus de lettres 1 que tout autre facteur de w de longueur k. Le nombre de mots préfixe normaux de longueur n est suite A194850 de l'OEIS. Asymptotiquement, ce nombre est $2^{n-\Theta (\log n)^{2}}$ (Paul Balister et Stefanie Gerke DOI 10.1016/j.tcs.2019.03.036). Autres détails dans : DOI 10.1016/j.tcs.2016.10.015
• mot privilégié : le mot vide, une lettre, ou récursivement un mot qui possède un bord privilégié qui apparaît exactement deux fois. Ce bord est alors son plus long bord. Un mot privilégié est toujours fermé, mais les mots $abab$, $ababab$, $ababbabab$, sont fermés sans être privilégiés. Les premiers mots privilégiés sont $\varepsilon ,a,b,aa,bb,aaa,aba,bab,bbb$.

R

• répétition : un mot de la forme $x^{k}y$, où k ≥ 2 est entier et y est un préfixe de x. Si k ≥ 1, on parle de sesquipuissance. On dit aussi puissance rationnelle (opposé à puissance entière)
• retourné d'un mot : Le retourné de $a_{1}\cdots a_{n}$ est $a_{n}\cdots a_{1}$. Il est noté $w^{\sim }$ ou ${\tilde {w}}$ ou $w^{R}$. Se dit aussi image miroir.
• mot de retour complet pour un mot $u$ : un mot qui commence par $u$, se termine par $u$ et ne contient pas $u$ en facteur interne, par exemple $aba$. $ababa$ est un mot de retour complet pour $aba$, mais pas pour $a$.
• mot de retour pour un mot $u$ : c'est un mot $v$ tel que $vu$ est un mot de retour complet. Par exemple, $ab$ est un mot de retour pour $aba$ dans $ababa$.
• suite récurrente : un mot infini qui contient tous ses facteurs une infinité de fois; ce n'est pas nécessairement une suite univers.
• mot récurrent : un mot infini $x$ est récurrent si tout facteur de $x$ apparaît une infinité de fois dans $x$. Voir aussi mot uniformément récurrent.
• mot riche : un mot qui possède le nombre maximum de facteurs palindromiques distincts. S'il est de longueur n, ce nombre est n+1 (en comptant le mot vide) (Complexité d'un mot#Mots riches en palindromes).

S

• sesquipuissance : désuet pour parler d'un mot de la forme $x^{k}y$, où k ≥ 1 et y est un préfixe de x. Si k ≥ 2, on dit répétition.
• morphisme simplifiable : $f:A^{*}\to B^{*}$ est simplifiable s'il existe $C$ avec $|C|<|B|$ tel que $f=h\circ g$ se factorise en $g:A^{*}\to C^{*}$ et $h:C^{*}\to B^{*}$. Exemple : $f:0\mapsto 0012,1\mapsto 12,2\mapsto 012$ se factorise par $g:0\mapsto 003,1\mapsto 3,2\mapsto 03$ et $h:0\mapsto 0,3\mapsto 12$.
• ensemble syndétique : un ensemble $S$ d'entiers naturels est syndétique s'il existe un entier $N$ tel la différence $t-s$ de deux éléments consécutifs $s<t$ de $S$, est bornée par $N$. Un mot infini $x$ est uniformément récurrent si, pour tout facteur $u$ de $x$, l'ensemble $S(u)$ des débuts d'occurrence de $u$ dans $x$ est syndétique.

U

• morphisme uniforme : un morphisme tel que les images des lettres ont toutes la même longueur. Si cette longueur est k, il est dit k-uniforme. Exemple : le morphisme de Thue-Morse $0\mapsto 01,1\mapsto 10$ est 2-uniforme.
• suite univers : un mot infini où tout mot fini apparaît comme facteur (donc une infinité de fois). Autres noms : suite disjonctive, suite de complexité maximale. Une suite univers est récurrente.
• mot uniformément récurrent : un mot infini $x$ tel que deux occurrences consécutives d'un facteur de $x$ sont à distance bornée. On dit aussi à lacunes bornées.

Z

• mot de Zimin : les mots définis par $Z_{n}=Z_{n-1}a_{n}Z_{n-1}$ ; les premiers sont : a, aba, abacaba.