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. Ils sont liés aux colliers ou mots circulaires. Un mot primitif est aussi appelé apériodique.

Définition

Un mot $x$ sur un alphabet $A$ est primitif s'il n’est pas une puissance d'un autre mot, donc s'il n'existe pas de mot $y\ne x$ tel que $x=y^n$ pour un entier naturel $n$ positif. 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,\dots$.

Propriétés

Unicité

Les propriétés suivantes se trouvent dans les manuels, comme ceux de Lothaire ou de Shallit Modèle:Théorème 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. Modèle:Théorème Prenons par exemple $x=abaab$. Ses conjugués sont

$abaab,baaba,aabab,ababa,babaa$.

Ils sont tous primitifs. Modèle:Théorème

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)=\frac{1}{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

$n{M}_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 Modèle: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

Modèle:Théorème 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\ge 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 $x{y}^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 $x{y}^m$ est imprimitif, alors $m\le 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 $x{y}^2=(aabab{)}^2$.

Mots sans bord

Modèle:Théorème 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. Modèle:Démonstration

Un lemme

Le résultat suivant est utile dans les démonstrations des propriétés des mots primitifs : Modèle:Théorème

Modèle:Démonstration 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 questionModèle:,. 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}^{\mathrm{\infty }}nM(n)=\sum _{n=0}^{\mathrm{\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 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. Modèle:Théorème

Bibliographie

• Modèle:Ouvrage — Une seconde édition révisée est parue chez Cambridge University Press, dans la collection Cambridge Mathematical Library, en 1997, Modèle:ISBN
• Modèle:Ouvrage

Articles liés

• Combinatoire
• Équation entre mots
• Mot de Lyndon
• Collier
• Mot circulaire
• Théorème de Chomsky-Schützenberger
• Lemme d'Ogden
• Code comma-free