Mot morphique

En mathématiques et informatique théorique, un mot morphique (ou une suite morphique) est un mot infini obtenu par itération d'un morphisme (appelé le générateur), suivie de l'application d'un morphisme préservant la longueur (appelé le morphisme de codage). Les mots morphiques sont une généralisation des suites automatiques, et comprennent certains mots sturmiens comme le mot de Fibonacci, et d'autres mots comme la suite caractéristique des carrés et des mots sans carré. Une classe particulière est constituée des mots purement morphiques : ce sont les mots où le morphisme de codage est l'identité.

Les mots morphiques sont plus stables pour les transformations simples que les morphismes purement morphiques ; de plus, de nombreuses propriétés sont décidables. Les mots morphiques sont de faible complexité : le nombre de facteurs de longueur donnée croît moins qu'exponentiellement. Il en résulte que le mot de Champernowne n'est pas une suite morphique.

Soit ${\displaystyle A}$ un alphabet. Un morphisme de monoïdes ${\displaystyle f:A^{*}\to A^{*}}$ est prolongeable pour une lettre ${\displaystyle a}$ de ${\displaystyle A}$ si ${\displaystyle a}$ est un préfixe propre de ${\displaystyle f(a)}$, et si de plus, la suite des longueurs de itérés ${\displaystyle f^{n}(a)}$ tend vers l'infini lorsque ${\displaystyle n}$ tend vers l'infini.

Si ${\displaystyle f:A^{*}\to A^{*}}$ est prolongeable en ${\displaystyle a}$, il existe un mot non vide ${\displaystyle u}$ tel que ${\displaystyle f(a)=au}$. En itérant, on obtient l'expression :

${\displaystyle f^{n}(a)=auf(u)\cdots f^{n-1}(u)}$

La suite de ces mots converge vers un mot infini noté ${\displaystyle f^{\omega }(a)}$ :

${\displaystyle f^{\omega }(a)=\lim _{n\to \infty }f^{n}(a)}$.

Ce mot est le mot infini engendré par ${\displaystyle f}$ en ${\displaystyle a}$. Le morphisme ${\displaystyle f}$ est parfois appelé un générateur du mot infini.

Un mot infini ${\displaystyle x}$ sur un alphabet ${\displaystyle A}$ est purement morphique s'il existe un morphisme ${\displaystyle f:A^{*}\to A^{*}}$ et une lettre ${\displaystyle a}$ dans ${\displaystyle A}$ tel que

${\displaystyle x=f^{\omega }(a)}$.

Un mot infini ${\displaystyle y}$ sur un alphabet ${\displaystyle B}$ est morphique s'il est l'image par un morphisme littéral (lettre à lettre) d'un mot purement morphique. Ce morphisme est appelé parfois morphisme de codage.

Ainsi, un mot morphique ${\displaystyle y}$ est défini par un triplet ${\displaystyle (a,f,h)}$, où ${\displaystyle a}$ est une lettre, ${\displaystyle f}$ est un morphisme prolongeable en ${\displaystyle a}$, et ${\displaystyle h}$ est un morphisme de codage. Le mot infini engendré par ce triplet est

${\displaystyle y=h(f^{\omega }(a))}$.

• Le morphisme de Thue-Morse ${\displaystyle \mu }$ est défini par${\displaystyle {\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &ba\end{array}}}$.Il est prolongeable à la fois en la lettre ${\displaystyle a}$ et en la lettre ${\displaystyle b}$. Pour la lettre ${\displaystyle a}$, on obtient le mot infini de Thue-Morse :${\displaystyle abbabaabbaababbabaababbaabbabaab\cdots }$et pour la lettre ${\displaystyle b}$, on obtient le mot opposé${\displaystyle baababbaabbabaababbabaabbaababba\cdots }$.Ce sont donc des mots purement morphiques.
• Le morphisme de Fibonacci est défini par${\displaystyle {\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &a\end{array}}}$.Il est prolongeable en ${\displaystyle a}$ ; en itérant, on obtient le mot infini :${\displaystyle abaababaabaababaababa\cdots }$.C'est un mot purement morphique.
• Le morphisme${\displaystyle {\begin{array}{rcl}a&\mapsto &a1\\1&\mapsto &001\\0&\mapsto &0\end{array}}}$est prolongeable en ${\displaystyle a}$. En itérant, on obtient le mot infini :${\displaystyle a1001000010000001000000001\cdots }$qui, à la première lettre près, est la suite caractéristique des carrés (0, 1, 4, 9, 16, etc). En lui appliquant le morphisme littéral qui identifie ${\displaystyle a}$ et ${\displaystyle 1}$, on obtient exactement la suite caractéristique, qui est donc un mot morphique. On peut vérifier facilement que cette suite n'est pas purement morphique : l'image de la lettre 1 doit commencer par le mot 110 (car si l'image est seulement 11, le mot infini engendré est ${\displaystyle 1^{\omega }}$). Mais alors, dès la deuxième itération, on produit un mot contenant deux facteurs 11, ce qui contredit le fait qu'il n'y a pas deux entiers consécutifs carrés à l'exception de 0 et 1.
• Lorsque le morphisme qui est itéré est uniforme, c'est-à-dire lorsque les images des lettres ont toutes la même longueur (par exemple, le morphisme de Thue-Morse est uniforme), la suite engendrée est une suite automatique. La suite ternaire de Thue-Morse${\displaystyle abcacbabcbacabcacbacabcb\cdots }$est à la fois un mot purement morphique, car engendré par le morphisme${\displaystyle {\begin{array}{rcl}a&\mapsto &abc\\b&\mapsto &ac\\c&\mapsto &b\end{array}}}$et une suite automatique, par la construction de Thue-Morse.

Un autre exemple de mot morphique sans être purement morphique a été donné par Abram, Hu et Li^[1]. Ce sont des mots qui comptent les occurrences de facteurs dans certains développements.

Soit ${\displaystyle m>1}$ un entier, soit ${\displaystyle A=\{0,\dots ,m-1\}}$, et soit ${\displaystyle w\in A^{+}}$. La suite de comptage de blocs est le mot infini

${\displaystyle (e_{w}(n))_{n\geq 0}}$

qui compte le nombre d'occurrences du mot ${\displaystyle w}$ dans le dévelopement en base ${\displaystyle m}$ des entiers consécutifs et

${\displaystyle (a_{w}(n))_{n\geq 0}}$

la suite d'entiers sur ${\displaystyle A}$ définie par

${\displaystyle a_{w}(n)=e_{w}(n){\bmod {m}}}$

La suite de Thue-Morse peut être définie ainsi : c'est la suite ${\displaystyle a_{w}(n)}$ pour le mot ${\displaystyle w=1}$. De même, la suite de Rudin-Shapiro est la suite ${\displaystyle a_{w}(n)}$ pour le mot ${\displaystyle w=11}$.

Les auteurs prouvent le résultat suivant^[1] :

Si l'entier ${\displaystyle m}$ est un nombre premier, alors la suite ${\displaystyle a_{w}(n)=e_{w}(n){\bmod {m}}}$ est uniformément morphique, c'est-à-dire engendré par un morphisme uniforme de taille m. De plus, elle est purement morphique si et seulement si ${\displaystyle w}$ est une lettre non nulle.

De plus, la série formelle ${\displaystyle \sum _{n=0}^{\infty }a_{w}(n)t^{n}}$ est algébrique de degré ${\displaystyle m}$ sur ${\displaystyle \mathbb {F} _{m}(t)}$.

À uu morphisme ${\displaystyle f:A^{*}\to A^{*}}$ est naturellement associé une ${\displaystyle A\times A}$-matrice ${\displaystyle M=M(f)=(m_{a,b})_{a,b\in A}}$, où ${\displaystyle m_{a,b}}$ est le nombre d'occurrences de la lettre ${\displaystyle a}$ dans le mot ${\displaystyle f(b)}$. Cette matrice est appelée la matrice d'incidence du morphisme ${\displaystyle f}$.

Pour la suite de Fibonacci, la matrice est :

${\displaystyle {\begin{bmatrix}1&1\\1&0\end{bmatrix}}}$,

pour la suite binaire de Thue-Morse, c'est :

${\displaystyle {\begin{bmatrix}1&1\\1&1\end{bmatrix}}}$,

pour la suite ternaire de Thue, c'est:

${\displaystyle {\begin{bmatrix}1&1&0\\1&0&1\\1&1&0\end{bmatrix}}}$,

pour la suite de carrés, la matrice est :

${\displaystyle {\begin{bmatrix}1&0&0\\1&1&0\\0&2&1\end{bmatrix}}}$.

Pour un mot w, on a la formule :

${\displaystyle {\begin{bmatrix}|f(w)|_{a}\\|f(w)|_{b}\\\vdots \\|f(w)|_{b}\end{bmatrix}}=M(f){\begin{bmatrix}|w|_{a}\\|w|_{b}\\\vdots \\|w|_{b}\end{bmatrix}}}$

et par itération :

${\displaystyle {\begin{bmatrix}|f^{n}(w)|_{a}\\|f(w)^{n}|_{b}\\\vdots \\|f^{n}(w)|_{b}\end{bmatrix}}=(M(f))^{n}{\begin{bmatrix}|w|_{a}\\|w|_{b}\\\vdots \\|w|_{b}\end{bmatrix}}}$

et aussi :

${\displaystyle |f^{n}(w)|={\begin{bmatrix}|1&1&\cdots &1\end{bmatrix}}=(M(f))^{n}{\begin{bmatrix}|w|_{a}\\|w|_{b}\\\vdots \\|w|_{b}\end{bmatrix}}}$

Une matrice ${\displaystyle M}$ à coefficients positifs ou nuls est primitive s'il existe un entier ${\displaystyle p}$ telle que les coefficients de la matrice ${\displaystyle M^{p}}$ sont tous non nuls. Si ${\displaystyle M}$ est primitive, un tel entier ${\displaystyle p}$ existe vérifiant ${\displaystyle p<n^{2}-2n+2}$, où ${\displaystyle n}$ est l'ordre de la matrice ${\displaystyle M}$.

Un morphisme ${\displaystyle f}$ est primitif si sa matrice d'incidence ${\displaystyle M(f)}$ est primitive. Seule la matrice du dernier exemple n'est pas primitive.

Dire que ${\displaystyle f:A^{*}\to A^{*}}$ est primitif revient à dire que pour un certain entier ${\displaystyle p}$, tous les mots ${\displaystyle f^{p}(b)}$, pour ${\displaystyle b}$ parcourant l'alphabet ${\displaystyle A}$, contient chacun toutes les lettres de l'alphabet au moins une fois. Par exemple, pour le morphisme ternaire ${\displaystyle \tau }$ de Thue

${\displaystyle {\begin{array}{rcl}a&\mapsto &abc\\b&\mapsto &ac\\c&\mapsto &b\end{array}}}$

on a ${\displaystyle \tau ^{3}(a)=abcacbabcbac\quad \tau ^{3}(b)=abcacbabc\quad \tau ^{3}(c)=abca}$.

Un matrice ${\displaystyle M=(m_{i,j})}$ d'ordre ${\displaystyle n}$ est irréductible si le graphe dont les arcs sont les couples ${\displaystyle (i,j)}$ tels que ${\displaystyle m_{i,j}\neq 0}$ est fortement connexe.

Si ${\displaystyle f:A^{*}\to A^{*}}$ est prolongeable en une lettre ${\displaystyle a}$ de ${\displaystyle A}$, et si ${\displaystyle M(f)}$ est irréductible, alors ${\displaystyle M(f)}$ (et donc ${\displaystyle f}$) est primitive. En effet, soient ${\displaystyle b}$ et ${\displaystyle c}$ deux lettre de ${\displaystyle A}$. Il existe, dans le graphe dont ${\displaystyle M}$ est la matrice d'adjacence, un chemin de ${\displaystyle b}$ vers ${\displaystyle a}$, et un chemin de ${\displaystyle a}$ vers ${\displaystyle c}$, tous deux de longueur au plus ${\displaystyle n}$. En parcourant une ou plusieurs fois, si nécessaire, la boucle autour de ${\displaystyle a}$, on obtient un chemin de longueur ${\displaystyle 2n}$ de ${\displaystyle b}$ vers ${\displaystyle c}$. Ceci montre que ${\displaystyle M^{2n}}$ a toutes ses coordonnées non nulles.

Soit ${\displaystyle x}$ un mot infini sur un alphabet ${\displaystyle A}$. Le mot ${\displaystyle x}$ est uniformément récurrent si, pour tout entier ${\displaystyle n}$, il existe un entier ${\displaystyle R(n)}$ tel que tout facteur de longueur ${\displaystyle R(n)}$ de ${\displaystyle x}$ contient tous les facteurs de longueur ${\displaystyle n}$ de ${\displaystyle x}$.

Si un mot morphique admet un générateur primitif, alors il est uniformément récurrent.^{[réf. nécessaire]}

Réciproquement, on a :

Si un mot morphique est uniformément récurrent, alors il possède un générateur primitif.^{[réf. nécessaire]}

L'image, par une morphisme, d'un mot morphique, est encore un mot morphique, s'il est infini^[2].

Ceci implique en particulier que le morphisme de codage, dans la définition des mots morphiques, peut être remplacé par un morphisme quelconque, même effaçant, pourvu que l'image du mot soit encore infinie.

Tout mot morphique peut être engendré avec un morphisme générateur non effaçant^[3]

Un morphisme ${\displaystyle f}$ est non effaçant si ${\displaystyle f(b)}$ n'est pas le mot vide pour toute lettre ${\displaystyle b}$.

La fonction de complexité ${\displaystyle c_{x}}$ d'un mot infini ${\displaystyle x}$ est la fonction qui, pour tout entier naturel ${\displaystyle n}$, donne le nombre ${\displaystyle c_{x}(n)}$ de facteur de ${\displaystyle x}$ de longueur ${\displaystyle n}$. Alors que la fonction de complexité d'un mot purement morphique peut se classer en quatre rubriques, les résultats pour les mots morphiques sont moins complets. On sait ^[4] :

Soit ${\displaystyle x}$ un mot infini binaire morphique. La fonction de complexité de ${\displaystyle x}$ vérifie l'une des propriétés suivantes

1. il existe un entier ${\displaystyle r\geq 1}$ tel que ${\displaystyle c_{x}(n)=\Theta (n{\sqrt[{r}]{n}})}$,
2. ${\displaystyle c_{x}(n)=O(n\log n)}$.

Il est décidable si un mot morphique ${\displaystyle x}$ est ultimement périodique, c'est-à-dire s'il existe des mots ${\displaystyle u}$ et ${\displaystyle v}$ tels que ${\displaystyle x=uv^{\omega }}$^[5].

Ce résultat était connu depuis longtemps pour les mots purement morphiques^[6].

Il est décidable si un mot morphique ${\displaystyle x}$ est uniformément récurrent^[7].

Dans un article publié sur Arxiv^[8], Allouche, Cassaigne, Shallit et Zamboni dressent des variantes dans la définition des mots morphiques, et donnent leurs propriétés respectives :

1. Mot purement morphique
2. Mot morphique : comme défini ici, un mot purement morphique suivi d'un codage (${\displaystyle 1\Rightarrow 2}$)
3. Mot purement morphique uniforme : le morphisme sousjacent est uniforme (${\displaystyle 3\Rightarrow 1}$)
4. Mot morphique uniforme (${\displaystyle 4\Rightarrow 2}$)
5. Mot purement morphique primitif (${\displaystyle 5\Rightarrow 1,6}$)
6. Mot morphique primitif: le morphisme est primitif (${\displaystyle 6\Rightarrow 2}$)
7. Mot purement morphique primitif uniforme (${\displaystyle 7\Rightarrow 1,\ldots ,6,8}$)
8. Mot morphique primitif uniforme (${\displaystyle 8\Rightarrow 2,4,6}$)
9. Mot uniformément récurrent (${\displaystyle 9\Rightarrow 10}$)
10. Mot récurrent.

Ces 10 propriétés, comme elles ne sont pas indépendantes, ne donnent lieu qu'à 20 cas distincts pour lesquels les auteurs fournissent des exemples^[8].

• Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit et Luca Q. Zamboni, « A Taxonomy of Morphic Sequences », Arxiv,‎ 29 novembre 2017 (DOI 10.48550/arXiv.1711.10807, lire en ligne)

• M. Lothaire, Combinatorics on Words, Reading, Mass., Addison-Wesley, 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).
• Jean-Paul Allouche et Jeffrey Shallit, Automatic Sequences : theory, applications, generalizations, Cambridge, Cambridge University Press, 2003, 571 p. (ISBN 0-521-82332-3)
• Valérie Berthé et Michel Rigo (éditeurs), Combinatorics, Automata and Number Theory, Cambridge University Press, coll. « Encyclopedia of mathematics and its applications » (n^o 135), 2010, 615 p. (ISBN 978-0-521-51597-9, lire en ligne)
• Fabien Durand, « Decidability of the HD0L ultimate periodicity problem », RAIRO - Theoretical Informatics and Applications, vol. 47, n^o 2,‎ 1^er avril 2013, p. 201–214 (DOI 10.1051/ita/2013035, arXiv 1111.3268v1, lire en ligne)

• Ivan Mitrofanov, « A proof for the decidability of HD0L ultimate periodicity », arXiv,‎ 2011 (arXiv 1110.4780)
• Ivan Mitrofanov, « On uniform recurrence of HD0L systems », arXiv,‎ 2011 (arXiv 1111.1999v2)
• Antoine Abram, Yining Hu et Shuo Li, « Block-counting sequences are not purely morphic », Advances in Applied Mathematics, vol. 155,‎ 1^er avril 2024, p. 102673 (ISSN 0196-8858, DOI 10.1016/j.aam.2024.102673, arXiv 2304.14595)

• Portail de l'informatique théorique
• Portail des mathématiques