Complexité abélienne d'un mot

Un article de Wikipédia, l'encyclopédie libre.

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[modifier | modifier le code]

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 est la fonction 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 sont . Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les quatre mots contenant deux occurrences de , et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.

Notations[modifier | modifier le code]

Soit un alphabet. L'image commutative d'un mot sur 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 , le vecteur de Parikh d'un mot sur est le vecteur de défini par

.

Ici, est le nombre de lettres qui apparaissent dans le mot .

Exemple
Soit un alphabet à trois lettres, et soit . Le vecteur de Parikh de est , parce qu'il y a quatre lettres , une lettre et deux lettres dans le mot .

La complexité abélienne d'un mot fini ou infini est la fonction notée qui, pour tout entier naturel , donne le nombre notée d e vecteurs de Parikh distincts de facteurs de longueur de . De manière pratique on regarde, pour chaque entier , les facteurs de longueur de , 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[modifier | modifier le code]

Mots de complexité maximale[modifier | modifier le code]

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

Propriété.- La complexité abélienne d'un mot infini sur lettres vérifie pour tout .

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

Mot de Thue-Morse[modifier | modifier le code]

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

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

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[modifier | modifier le code]

Un mot sturmien est un mot infini binaire qui a exactement facteurs de longueur , pour tout entier naturel . 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 , pour tout entier , deux facteurs et de longueur on même nombre d'occurrences de chaque lettre, à 1 près. Traduit en vecteurs de Parikh, cela signifie que les vecteurs de Parikh et ne peuvent prendre que deux valeurs différentes. On a ainsi établi[1] :

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

La complexité abélienne du mot de Tribonacci[modifier | modifier le code]

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

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

Chaque mot est obtenu par concaténation des trois mots précédents. En notant le e mot, on a donc

.

Cela résulte du fait que

.

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

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

Propriété.- La complexité abélienne du mot de Tribonacci prend les valeurs , et ces valeurs seulement : pour tout . De plus, chaque valeur est atteinte une infinité de fois[3].

Équivalence k-commutative[modifier | modifier le code]

Deux mots sont commutativement équivalents à l'ordre , ou -commutativement équivalents s'il chaque facteur de longueur au plus apparaît le même nombre de fois dans chacun des deux mots[4]. Pour , on retrouve l'équivalence commutative, et pour , on obtient l'égalité.

Formellement, deux mots et sont -commutativement équivalents, et on écrit si pour tout mot de longueur . Ici on note le nombre d’occurrences du mot comme facteur dans .

Si , on retrouve la notion d’équivalence commutative ; si , alors si et seulement si.

Exemple. Les mots et 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 et pas dans .

Exemple. Les mots et 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 , on note la fonction de complexité -abélienne d'un mot qui donne, pour chaque entier , le nombre de classes de la relation \sim_k, donc le nombre de facteurs de de longueur distincts à -commutativité près. dénote la complexité commutative, et est la fonction de complexité usuelle qui compte le nombre de facteurs distincts.

Il est commode d'introduire une fonction auxiliaire définie par

.

La suite des valeurs prises par cette fonction est .

Propriété.- Si la complexité -abélienne d'un mot infini vérifie pour tout , alors 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 est égale à est sturmien.

Notes et références[modifier | modifier le code]

  1. a et b Richomme, Saari et Zamboni 2011.
  2. Richomme, Saari et Zamboni 2010.
  3. Par la dernière phrase, (Turek 2013) répond ainsi positivement à une question posée dans (Richomme, Saari et Zamboni 2010).
  4. Karhumaki, Saarela et Zamboni 2013.

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • Gwenaël Richomme, Kalle Saari et Luca Q. Zamboni, « Abelian complexity of minimal subshifts », Journal of the London Mathematical Society, vol. 83, no 1,‎ , 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,‎ , p. 212–231.
  • Ondřej Turek, « Abelian complexity and abelian co-decomposition », Theoretical Computer Science, vol. 469,‎ , 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, no 8,‎ , 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, nos 1-4,‎ , 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, no 2,‎ , 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,‎ , 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 »,‎ , 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,‎ , article no 105524 (DOI 10.1016/j.jcta.2021.105524)
  • Gabriele Fici et Svetlana Puzynina, « Abelian Combinatorics on Words: a Survey », Computer Science Review, vol. 47,‎ , article no 105524 (DOI 10.1016/j.cosrev.2022.100532, arXiv 2207.09937)