Complexité abélienne d'un mot

Modèle:Article principal En informatique théorique, et notamment en combinatoire des mots, il existe plusieurs manières de cerner la complexité d'une suite infinie de symboles, parmi lesquelles il y a la complexité algorithmique ou la complexité de Kolmogorov. D'autres mesures, plus arithmétique ou combinatoire, sont la complexité en facteurs, en anglais « subword complexity », la complexité palindromique qui compte le nombre de palindromes, ou la complexité arithmétique. La complexité abélienne est encore une autre mesure de la « complexité combinatoire » d'une suite.

Équivalence commutative ou abélienne

Deux mots sont commutativement équivalents ou équivalents au sens abélien s'ils ont même image commutative, autrement dit s'ils sont les mêmes à une permutation de lettres près, ou encore s'ils sont des anagrammes l'un de l'autre.

La complexité abélienne d'un mot fini ou infini $x$ est la fonction $p_x$ qui compte le nombre de 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.

Exemple. Les 7 facteurs de longueur 6 du mot de Fibonacci $010010100100101001010\cdots$ sont Modèle:Indente Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les cinq mots contenant deux occurrences de $1$, et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.

Notations

Soit $A$ un alphabet. L'image commutative d'un mot $w$ sur $A$ est l'image, dans le monoïde commutatif libre, de ce mot. On appelle souvent cette image le vecteur de Parikh du mot, d'après le mathématicien Rohit Parikh qui l'a considéré le premier dans le cadre d'un travail sur l'image commutative de langages algébriques. Si $A=\{a_1,a_2,\dots ,a_n\}$, le vecteur de Parikh d'un mot $w$ sur $A$ est le vecteur $\mathrm{\Psi }(w)$ de ${\mathbb{N}}^n$ défini par

$\mathrm{\Psi }(w)=(|w{]}_{a_1},|w{]}_{a_2},\dots ,|w{]}_{a_n})$.

Ici, $|w{]}_a$ est le nombre de lettres $a$ qui apparaissent dans le mot $w$.

Exemple

Soit $A=\{0,1,2\}$ un alphabet à trois lettres, et soit $w=0120200$. Le vecteur de Parikh de $w$ est $\mathrm{\Psi }(w)=(4,1,2)$, parce qu'il y a quatre lettres $0$, une lettre $1$ et deux lettres $2$ dans le mot $w$.

La complexité abélienne d'un mot fini ou infini $x$ est la fonction notée $p_x$ qui, pour tout entier naturel $n$, donne le nombre notée $p_x(n)$d e vecteurs de Parikh distincts de facteurs de longueur $n$ de $x$. De manière pratique on regarde, pour chaque entier $n$, les facteurs de longueur $n$ de $x$, et on les groupe en paquets contenant les facteurs de même image commutative. Le nombre de paquets est le nombre cherché.

Exemples de complexité abélienne

Mots de complexité maximale

La propriété suivante est facile à vérifier.

Propriété.- La complexité abélienne d'un mot infini $x$ sur $k$ lettres vérifie Modèle:Indente pour tout $n\ge 1$.

Cette borne est atteinte par la suite de Champernowne par exemple.

Mot de Thue-Morse

Le mot de Thue-Morse $t$ a la fonction de complexité suivante :

$p_t(n)=\{\begin{array}{cc}2& n\text{ impair }\\ 3& n>0\text{ pair. }\end{array}$

En fait, une sorte de réciproque est vraie aussi:

Propriété.- Si un mot infini binaire récurrent a la même fonction de complexité et la même fonction de complexité abélienne que le mot de Thue-Morse, alors il a les mêmes facteurs.

Mots sturmiens

Un mot sturmien est un mot infini binaire qui a exactement $n+1$ facteurs de longueur $n$, pour tout entier naturel $n$. L'exemple paradigmatique de mot sturmien est le mot de Fibonacci.

Parmi les nombreuses propriétés des mots sturmiens, il y a celle qui dit que les mots sturmiens sont équilibrés : dans un mot sturmien $x$, pour tout entier $n$, deux facteurs $u$ et $v$ de longueur $n$ on même nombre d'occurrences de chaque lettre, à 1 près. Traduit en vecteurs de Parikh, cela signifie que les vecteurs de Parikh $\mathrm{\Psi }(u)$ et $\mathrm{\Psi }(v)$ ne peuvent prendre que deux valeurs différentes. On a ainsi établi :

Propriété.- La complexité abélienne d'un mot sturmien $x$ est la fonction constante égale à $2$. Réciproquement, un mot apériodique qui a complexité abélienne constante égale à $2$ est sturmien.

La complexité abélienne du mot de Tribonacci

Le mot de Tribonacci est défini par itération du morphisme :

$f:\begin{array}{ccc}0& \mapsto & 01\\ 1& \mapsto & 02\\ 2& \mapsto & 0\end{array}$

On obtient par itération la suite de mots suivants :

$\begin{array}{c}0\\ 01\\ 01|02\\ 0102|01|0\\ 0102010|0102|01\\ 0102010010201|0102010|0102\end{array}$

Chaque mot est obtenu par concaténation des trois mots précédents. En notant $t_n=f^n(0)$ le $n$Modèle:E mot, on a donc

$t_{n+3}=t_{n+2}{t}_{n+1}{t}_n$.

Cela résulte du fait que

$f^3(0)=f^2(01)=f^2(0)f^2(1)=f^2(0)f(02)=f^2(0)f(0)0$.

Le mot infini obtenu à la limite est le mot infini de Tribonacci. Il est noté $t$. C'est donc un mot purement morphique.

On a une propriété analogue à la précédente, pour le mot de Tribonacci :

Propriété.- La complexité abélienne $p_t$ du mot de Tribonacci $t$ prend les valeurs $3,4,5,6,7$, et ces valeurs seulement : $p_t(n)\in \{3,4,5,6,7\}$ pour tout $n$. De plus, chaque valeur est atteinte une infinité de fois.

Équivalence Modèle:Math-commutative

Deux mots sont commutativement équivalents à l'ordre $k$, ou $k$-commutativement équivalents s'il chaque facteur de longueur au plus $k$ apparaît le même nombre de fois dans chacun des deux mots. Pour $k=1$, on retrouve l'équivalence commutative, et pour $k=\mathrm{\infty }$, on obtient l'égalité.

Formellement, deux mots $x$ et $y$ sont $k$-commutativement équivalents, et on écrit $x{\sim }_{k}y$ si $|x{|}_u=|y{|}_u$ pour tout mot $u$ de longueur $|u|\le k$. Ici on note $|w{|}_u$ le nombre d’occurrences du mot $u$ comme facteur dans $w$.

Si $k=1$, on retrouve la notion d’équivalence commutative ; si $|x|=|y|\le k$, alors $x{\sim }_{k}y$ si et seulement si$x=y$.

Exemple. Les mots $x=010110$ et $y=011010$ sont 3-commutativement équivalents (0 et 1 apparaissant chacun 3 fois; 01 et 10 chacun 2 fois etc), mais ils ne sont pas 4-commutativement équivalents puisque 0101 apparaît dans $u$ et pas dans $v$.

Exemple. Les mots $x=0110$ et $y=1101$ ne sont pas 2-commutativement équivalents : ils ont les mêmes facteurs de longueur 2, mais ils ne sont pas commutativement équivalents.

Pour un entier $k$, on note $p_x^{(k)}$ la fonction de complexité $k$-abélienne d'un mot $x$ qui donne, pour chaque entier $n$, le nombre de classes de la relation \sim_k, donc le nombre de facteurs de $x$ de longueur $n$ distincts à $k$-commutativité près. $p_x^{(1)}$ dénote la complexité commutative, et $p_x^{(\mathrm{\infty })}$ est la fonction de complexité usuelle qui compte le nombre de facteurs distincts.

Il est commode d'introduire une fonction auxiliaire $q^{(k)}$ définie par

$q^{(k)}(n)=\{\begin{array}{cc}n+1& n<2k\\ 2k& n\ge 2k\end{array}$.

La suite des valeurs prises par cette fonction est $(1,2,3,\dots ,2k-1,2k,2k,\dots )$.

Propriété.- Si la complexité $k$-abélienne d'un mot infini $x$ vérifie $p_x^{(k)}(n)<q^{(k)}(n)$ pour tout $n$, alors $x$ est ultimement périodique.

La caractérisation des mots sturmiens par leur fonction e complexité abélienne se généralise comme suit :

Propriété.- Un mot apériodique dont la complexité k-abélienne $p_x^{(k)}=$ est égale à $q^{(k)}$ est sturmien.

Annexes

Articles connexes

• Mot morphique
• Mot automatique
• Combinatoire des mots
• Longueur palindromique d'un mot

Bibliographie

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article.
• Modèle:Article
• Modèle:Article
• Modèle:Article
• Modèle:Article

Modèle:Portail