Complexité abélienne d'un mot

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 6 facteurs de longueur 6 du mot de Fibonacci $010010100100101001010\cdots$ sont $001010,010010,010100,100100,100101,101001$. Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les quatre 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},\ldots ,a_{n}\}$, le vecteur de Parikh d'un mot $w$ sur $A$ est le vecteur $\Psi (w)$ de $\mathbb {N} ^{n}$ défini par

$\Psi (w)=(|w]_{a_{1}},|w]_{a_{2}},\ldots ,|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 $\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 $p_{x}(n)\leq {\binom {n+k-1}{k-1}}$ pour tout $n\geq 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{cases}2&n{\text{ impair }}\\3&n>0{\text{ pair. }}\end{cases}}$

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 $\Psi (u)$ et $\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}{rcl}0&\mapsto &01\\1&\mapsto &02\\2&\mapsto &0\end{array}}$

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

${\begin{array}{l}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$^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 k-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=\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|\leq 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|\leq 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}^{(\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{cases}n+1&n<2k\\2k&n\geq 2k\end{cases}}$.

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

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

• Gwenaël Richomme, Kalle Saari et Luca Q. Zamboni, « Abelian complexity of minimal subshifts », Journal of the London Mathematical Society, vol. 83, n^o 1,‎ 2011, p. 79-95 (DOI 10.1112/jlms/jdq063).
• Gwenaël Richomme, Kalle Saari et Luca Q. Zamboni, « Balance and Abelian complexity of the Tribonacci word », Advances in Applied Mathematics, vol. 45,‎ 2010, p. 212–231.
• Ondřej Turek, « Abelian complexity and abelian co-decomposition », Theoretical Computer Science, vol. 469,‎ 2013, p. 77-91.
• Juhani Karhumaki, Aleksi Saarela et Luca Q. Zamboni, « On a generalization of Abelian equivalence and complexity of infinite words », Journal of Combinatorial Theory, Series A, vol. 120, n^o 8,‎ 2013, p. 2189–2206 (ISSN 0097-3165, DOI 10.1016/j.jcta.2013.08.008).
• Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina et Markus A. Whiteland, « k-Abelian equivalence and rationality », Fundamenta Informaticae, vol. 154, n^os 1-4,‎ 2017, p. 65–94 (ISSN 0169-2968, DOI 10.3233/FI-2017-1553).
• Sergey Avgustinovich et Svetlana Puzynina, « Weak Abelian periodicity of infinite words », Theory of Computing Systems, vol. 59, n^o 2,‎ 2016, p. 161–179 (ISSN 1432-4350, DOI 10.1007/s00224-015-9629-1).
• Jin Chen et Zhi-Xiong Wen, « On the abelian complexity of generalized Thue-Morse sequences », Theoretical Computer Science, vol. 780,‎ 2019, p. 66–73 (DOI 10.1016/j.tcs.2019.02.014)
• Svetlana Puzynina, « Abelian properties of words », Lecture Notes in Computer Science, vol. 11682 « WORDS »,‎ 2019, p. 28-45 (DOI 10.1007/978-3-030-28796-2_2)
• Svetlana Puzynina et Markus Whiteland, « Abelian closures of infinite binary words », Journal of Combinatorial Theory, Series A, vol. 185,‎ 2022, article n^o 105524 (DOI 10.1016/j.jcta.2021.105524)
• Gabriele Fici et Svetlana Puzynina, « Abelian Combinatorics on Words: a Survey », Computer Science Review, vol. 47,‎ février 2023, article n^o 105524 (DOI 10.1016/j.cosrev.2022.100532, arXiv 2207.09937)