Mot primitif

En informatique théorique, en combinatoire, et notamment en combinatoire des mots, un mot primitif est un mot qui n’est pas une puissance d'un autre mot. Par exemple, abba est un mot primitif et abab n'est pas primitif puisqu'il est le carré du mot ab. Les mots primitifs représentent en quelque sorte l'équivalent combinatoire des nombres premiers en arithmétique. Les mots primitifs interviennent dans divers domaines, comme les équations entre mots, les mots de Lyndon, les langages formels, l'étude des colliers ou mots circulaires. Un mot primitif est aussi appelé apériodique.

Définition

Un mot $x$ est primitif s'il ne s'écrit pas $x=u^{k}$ , avec $k\geq 2$ .

Exemples

Le mot vide n’est pas primitif.

Pour un alphabet à deux lettres $a,b,$ les premiers mots primitifs sont :

a,b,ab,ba,aab,aba,abb,baa,bab,bba,aaab,\ldots

.

Propriétés

Unicité

Les propriétés suivantes se trouvent dans les manuels, comme ceux de Lothaire ou de Shallit

Propriété 1 — Tout mot s'écrit de manière unique comme puissance d'un mot primitif.

On trouve parfois le nom « racine » de $x$ pour désigner l'unique mot primitif dont $x$ est une puissance ; il est aussi noté ${\sqrt {x}}$ . L'entier $n$ tel que $x={\sqrt {x}}^{n}$ est l'« exposant » de $x$ . Par exemple, pour $x=ababab$ , ${\sqrt {x}}=ab$ et $x=(ab)^{3}$ , d'exposant 3. La propriété se démontre à l'aide du lemme ci-dessous.

Propriété 2 — Les conjugués d'un mot primitif sont eux-mêmes primitifs.

Prenons par exemple $x=abaab$ . Ses conjugués sont

abaab,baaba,aabab,ababa,babaa

.

Ils sont tous primitifs.

Propriété 3 — La classe de conjugaison d'un mot primitif de longueur $n$ a $n$ éléments.

Nombre de mots primitifs

Comme les conjugués d'un mot primitif sont tous distincts, car s'il y en avait deux égaux, ils vérifieraient une équation décrite dans le lemme ci-dessous, et seraient puissances d'un troisième mot, donc imprimitifs. La classe de conjugaison d'un mot primitif, ou de manière équivalent le mot circulaire associé à ce mot, est appelé un collier apérodique. Le nombre de colliers apériodiques de longueur $n$ , donc le nombre de classes de conjugaison de mots primitifs de longueur longueur n sur un alphabet à k lettres est

M_{k}(n)={1 \over n}\sum _{d\mid n}\mu (d)k^{n/d}

.

Ici, $\mu$ est la fonction de Möbius. Comme les conjugués d'un mot primitif sont tous primitifs et distincts, le nombre de mots primitifs de longueur longueur n sur un alphabet à k lettres est

nM_{k}(n)=\sum _{d\mid n}\mu (d)k^{n/d}

.

Les fonctions $M_{k}(n)$ sont aussi appelés les polynômes de colliers (en la variable $k$ ), et la formule est attribuée au colonel Moreau. Pour $k=2$ , la suite des $M_{k}(n)$ est la suite A001037 de l'OEIS. Pour $n=3$ et $n=4$ , les colliers apériodiques binaires sont respectivement 001,011 et 0001,0011,0111.

Le nombre $M_{k}(n)$ est le nombre de mots de Lyndon de longueur $n$ sur $k$ lettres : Toute classe de conjugaison d'un mot primitif contient un seul élément qui est plus petit que les autres dans un ordre lexicographique fixé, et c'est l'unique mot de Lyndon de la classe, de sorte que les mots de Lyndon forment un système de représentants des classes de mots primitifs ou de colliers apériodiques.

Théorème de Lyndon et Schützenberger

Propriété 4 — Si $x$ et $y$ sont deux mots primitifs distincts, alors $x^{n}y^{m}$ est un mot primitif pour tout $n,m\geq 2$ . De plus, au plus un des mots $x^{n}y^{m}$ pour $n,m\geq 1$ n'est pas primitif.

La première partie de cette propriété est en fait une paraphrase du théorème de Lyndon et Schützenberger qui dit que si $x^{n}y^{m}=z^{p}$ pour $n,m,p\geq 2$ , alors $x,y$ et $z$ ont même racine. Ceci n'est plus vrai si $n=1$ ou $m=1$ . Ainsi, pour $x=aba$ et $y=baab$ , le mot $x^{2}y=abaababaab$ est un carré. La deuxième partie de l'énoncé dit qu'au plus l'un des mots $x^{n}y$ ou $xy^{m}$ n'est pas primitif. Si $x$ et $y$ sont de même longueur, alors le seul mot éventuellement imprimitif est $xy$ . Par exemple, si $x=aba$ et $y=bab$ , alors $xy=(ab)^{3}$ . On peut montrer que dans le cas général, si $xy^{m}$ est imprimitif, alors $m\leq M$ , avec $M=2+(|x|-2)/|y|$ . Ainsi, pour $x=aababa$ et $y=ab$ , on a $M=2+(|x|-2)/|y|=2+(6-2)/2=4$ , et pour $m=2$ , on a $xy^{2}=(aabab)^{2}$ .

Mots sans bord

Propriété 5 — Un mot est primitif si et seulement si l'un de ses conjugués est un mot sans bord.

Un bord d'un mot $w$ est un mot qui est à la fois un préfixe propre et un suffixe propre de $w$ . Un mot sans bord est un mot qui ne possède pas de bord non vide.

Démonstration

Si $w$ n'est pas primitif, donc de la forme $w=y^{n}$ pour $n\geq 2$ , alors $y$ est un bord de $w$ , et tous les conjugués de $w$ sont des puissances d'un conjugué de $w$ , donc ont tous un bord.

Supposons maintenant que $w$ est primitif, et soit $x$ le plus petit des conjugués de $w$ dans un ordre lexicographique fixé. On prouve que $x$ est sans bord. En effet, supposons au contraire que $x$ a un bord $u$ . Alors $x=uvu$ pour $u$ non vide, et $v$ n’est pas vide sinon $x$ (et donc $w$ ) est un carré. Le mot $z=uuv$ est un conjugué de $x$ et donc de $w$ . Si $x=z$ , alors $uvu=uuv$ , donc $vu=uv$ et $x$ est au moins un cube par le lemme ci-dessous. Donc $x<z$ par la minimalité de $x$ , donc aussi $vu<uv$ . Mais alors $vuu<uvu=x$ , et $vuu$ est un conjugué de $w$ plus petit que $x$ , en contradiction avec l'hypothèse.

Un lemme

Le résultat suivant est utile dans les démonstrations des propriétés des mots primitifs :

Théorème — Soient $x$ et $y$ sont deux mots non vides. Les conditions suivantes sont équivalentes:

$xy=yx$ ,
il existe deux entiers $n,m\geq 1$ tels que $x^{n}=y^{m}$ ,
il existe un mot $z$ et deux entiers $p,q\geq 1$ tels que $x=z^{p}$ et $y=z^{q}$ .

Démonstration

$(3)\implies (2)$ . Avec (3), on a $x^{q}=(z^{p})^{q}=(z^{q})^{p}=y^{p}$ , donc (2).
$(2)\implies (1)$ . Si $x^{n}=y^{m}$ , alors $yx^{n}=y^{m+1}=y^{m}y=x^{n}y$ , et ce mot commence à la fois par $xy$ et par $yx$ , donc (1).
$(1)\implies (3)$ . Par récurrence sur $|x|+|y|$ . On peut supposer que $x$ est préfixe de $y$ , sinon on échange les rôles de $x$ et $y$ . Si $|x|=|y|$ , alors $x=y$ ; si $x$ est un préfixe propre de $y$ , il existe un mot non vide $t$ tel que $y=xt$ . En substituant dans l'équation, on obtient $xxt=xtx$ , et en simplifiant $xt=zt$ . Par récurrence, $x=z^{p}$ et $t=z^{q}$ pour un mot $z$ , et aussi $y=xt=z^{p+q}$ .

Ainsi, pour démontrer que tout mot a une racine unique, on peut supposer qu'un mot $w$ s'écrit de deux façons comme puissance d'un mot primitif, soit $w=x^{n}=y^{m}$ avec $x$ et $y$ des mots primitifs. Par la condition (3), il en résulte que $x=z^{p}$ et $y=z^{q}$ , et comme $x$ et $y$ sont primitifs, on a $p=q=1$ et $x=y$ .

Le langage des mots primitifs

Il est de tradition de noter $Q$ l'ensemble des mots primitifs sur un alphabet fixé. Sur une lettre, il n'y a qu'un seul mot primitif. Sur plus d'une lettre, le problème de la nature de l'ensemble $Q$ , dans le cadre de la théorie des langages formels, a été posé sans être encore résolu (en 2016). Pál Dömösi et Masami Ito ont consacré un ouvrage de plus de 500 pages à cette question^,. Un article de synthèse est de Gerhard Lischke.

On ne sait pas si le langage $Q$ est algébrique. Holger Petersen a prouvé, dans un article paru en 1996, que le langage $Q$ n'est pas algébrique inambigu. Il utilise pour cela la série génératrice du nombre de mots de $Q$ sur k lettres qui s'écrit

Q(z)=\sum _{n=0}^{\infty }nM(n)=\sum _{n=0}^{\infty }\sum _{d\mid n}\mu (d)k^{n/d}

et s'appuie sur le théorème de Chomsky-Schützenberger selon lequel la série génératrice du nombre de mots d’un langage algébrique inambigu est une fonction algébrique. Pour montrer que la série $Q(z)$ n'est pas algébrique, il applique l'un des critères développés par Philippe Flajolet.

Les outils usuels pour prouver qu'un langage n'est pas algébrique, comme le lemme d'itération d'Ogden, ou d'autres lemmes d'itération comme le lemme de Bader et Moura ou même le lemme d'échange d'Ogden, Winklmann et Ross, ne permettent pas de conclure.

Le langage $Q$ des mots primitifs est la fermeture, par permutation circulaire, du langage $L$ des mots de Lyndon. Si $L$ était algébrique, il en serait de même de $Q$ puisque les langages algébriques sont fermés par permutation circulaire. Or il a été démontré par Berstel et Boasson que $L$ n'est pas algébrique en appliquant le lemme d'Ogden.

Le langage $Q$ n'est pas non plus algébrique linéaire, mais c'est un langage contextuel déterministe, c'est-à-dire reconnu par un automate linéairement borné déterministe. Quant à la complexité de reconnaissance, le langage est dans la classe DTIME(n^2), c'est-à-dire qu'il est reconnu par une machine de Turing déterministe en temps quadratique.

Morphisme préservant les mots primitifs

Un morphisme d'un demi-groupe libre dans un deuxième demi-groupe libre préserve les mots primitifs si l'image d'un mot primitif est toujours un mot primitif.

Des exemples de morphismes préservant les mots primitifs sont fournis par les morphismes de Lyndon qui sont, par définition, les morphismes qui préservent les mots de Lyndon. Un tel morphisme $f$ préserve aussi les mots primitifs : en effet, si $x$ est un mot primitif, il existe un conjugué $y$ de $x$ qui est un mot de Lyndon ; l'image $f(y)$ de $y$ est par hypothèse un mot de Lyndon, donc primitif, et l'image $f(x)$ de $x$ , qui est un mot conjugué de $f(y)$ , est donc aussi un mot primitif. Une étude détaillée des morphismes préservant les mots primitifs a été faite par Viktor Mitrana. Une version longue est disponible en ligne. Le résultat principal est une caractérisation des morphismes préservant les mots primitifs. Pour cela, on définit la notion de code pur. Un code à longueur variable $X$ est un code pur si, pour tout élément $x$ de $X^{+}$ , la racine ${\sqrt {x}}$ est également élément de $X^{+}$ . On peut montrer qu'un code est pur si et seulement si $X^{*}$ est un langage sans étoile.

Proposition — Un morphisme $f:A^{+}\to B^{+}$ préserve les mots primitifs si et seulement si $f(A)$ est un code pur.

Notes et références

↑ Lothaire 1983.
↑ Shallit 2009, p. théorème 2.3.4.
↑ Lischke attribue ce résultat à Huei-Jan Shyr et Shyr-Shen Yu, « Non-primitive words in the language $p^{+}q^{+}$ », Soochow J. Math., vol. 20, n^o 4,‎ 1994, p. 535–546.
↑ Othman Echi, « Non-primitive words of the form pq^m », RAIRO - Theoretical Informatics and Applications, vol. 51, n^o 3,‎ 2017, p. 141-166 (ISSN 0988-3754, DOI 10.1051/ita/2017012)
↑ Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 520 p. (ISBN 978-981-4271-66-0, OCLC 897020798)
↑ C'est surtout le chapitre 8 du livre, intitulé Some Properties of the Language of Primitive Words, qui étudie l'algébricité du langage.
↑ Gerhard Lischke, « Primitive words and roots of words », Acta Univ. Sapientiae, Informatica, vol. 3, n^o 1,‎ 2011, p. 5–34 (arXiv 1104.4427).
↑ Holger Petersen, « On the Language of Primitive Words », Theoretical Computer Science, vol. 161, n^os 1-2,‎ 1996, p. 141-156 (lire en ligne).
↑ (en) Philippe Flajolet, « Analytic models and ambiguity of context-free languages », Theoret. Comput. Sci., vol. 49,‎ 1987, p. 283-309 (DOI 10.1016/0304-3975(87)90011-9, lire en ligne).
↑ Jean Berstel et Luc Boasson, « The set of Lyndon words is not context-free », Bulletin of the European Association for Theoretical Computer Science 63 (1997), vol. 63, n^o 1,‎ 1997, p. 139-140.
↑ Lischke 2011.
↑ On trouve parfois le terme « morphisme primitif » pour un morphisme préservant les mots primitifs, mais ce terme est maintenant plutôt réservé, en combinatoire des mots, à un morphisme dont la matrice associée est primitive.
↑ Gwénaël Richomme, « Quelques éléments de Combinatoire des Mots Cours 2014-2015 », Lirmm, 2014-2015 (consulté le 6 mai 2017).
↑ Victor Mitrana, « Primitive morphisms », Information Processing Letters, vol. 64,‎ 1997, p. 277–281.
↑ Victor Mitrana, « On morphisms preserving primitive words », TUCS Technical Report N° 69, Turku Center for Computer Science, novembre 1996 (ISBN 951-650-895-2, consulté le 6 mai 2017).

Bibliographie

M. Lothaire, Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (n^o 17), 1983, 238 p. (ISBN 978-0-201-13516-9, présentation en ligne) — Une seconde édition révisée est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, (ISBN 978-0521599245)
(en) Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press, 2009, 240 p. (ISBN 978-0-521-86572-2)

Articles liés

Portail de l'informatique théorique

[1] Lothaire 1983.

[2] Shallit 2009, p. théorème 2.3.4.

[3] Lischke attribue ce résultat à Huei-Jan Shyr et Shyr-Shen Yu, « Non-primitive words in the language $p^{+}q^{+}$ », Soochow J. Math., vol. 20, n^o 4,‎ 1994, p. 535–546.

[Echi2017-4] Othman Echi, « Non-primitive words of the form pq^m », RAIRO - Theoretical Informatics and Applications, vol. 51, n^o 3,‎ 2017, p. 141-166 (ISSN 0988-3754, DOI 10.1051/ita/2017012)

[5] Pál Dömösi et Masami Ito, Context-free languages and primitive words, World Scientific Publishing, 2014, 520 p. (ISBN 978-981-4271-66-0, OCLC 897020798)

[6] C'est surtout le chapitre 8 du livre, intitulé Some Properties of the Language of Primitive Words, qui étudie l'algébricité du langage.

[7] Gerhard Lischke, « Primitive words and roots of words », Acta Univ. Sapientiae, Informatica, vol. 3, n^o 1,‎ 2011, p. 5–34 (arXiv 1104.4427).

[8] Holger Petersen, « On the Language of Primitive Words », Theoretical Computer Science, vol. 161, n^os 1-2,‎ 1996, p. 141-156 (lire en ligne).

[9] (en) Philippe Flajolet, « Analytic models and ambiguity of context-free languages », Theoret. Comput. Sci., vol. 49,‎ 1987, p. 283-309 (DOI 10.1016/0304-3975(87)90011-9, lire en ligne).

[10] Jean Berstel et Luc Boasson, « The set of Lyndon words is not context-free », Bulletin of the European Association for Theoretical Computer Science 63 (1997), vol. 63, n^o 1,‎ 1997, p. 139-140.

[11] Lischke 2011.

[12] On trouve parfois le terme « morphisme primitif » pour un morphisme préservant les mots primitifs, mais ce terme est maintenant plutôt réservé, en combinatoire des mots, à un morphisme dont la matrice associée est primitive.

[13] Gwénaël Richomme, « Quelques éléments de Combinatoire des Mots Cours 2014-2015 », Lirmm, 2014-2015 (consulté le 6 mai 2017).

[14] Victor Mitrana, « Primitive morphisms », Information Processing Letters, vol. 64,‎ 1997, p. 277–281.

[15] Victor Mitrana, « On morphisms preserving primitive words », TUCS Technical Report N° 69, Turku Center for Computer Science, novembre 1996 (ISBN 951-650-895-2, consulté le 6 mai 2017).