Mot morphique

Morphisme prolongeable

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.

Mot morphique

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))}$.

Premiers exemples

• 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

Un autre exemple de mot morphique sans être purement morphique a été donné par Abram, Hu et Li. 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éveloppement 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 :

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)}$.

Exemples

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}}}$

Morphisme irréductible et morphisme primitif

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.

Récurrence uniforme

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]}

Assouplissement des hypothèses

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

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.

Renforcement des hypothèses

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

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

Complexité des mots morphiques

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 :

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)}$.

Problèmes de décision

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 }}$.

Ce résultat était connu depuis longtemps pour les mots purement morphiques.

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

Références

Bibliographie

• 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).
• (en) 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, article n^o 102673 (ISSN 0196-8858, DOI 10.1016/j.aam.2024.102673, arXiv 2304.14595)

• Golnaz Badkobeh et Pascal Ochem, « More characterizations of morphic words », Theoretical Computer Science,‎ 7 mars 2026, article n^o 115875 (DOI 10.1016/j.tcs.2026.115875, arXiv 2312.10757, lire en ligne)

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