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.

Définition

Morphisme prolongeable

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

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

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

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

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

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

Mot morphique

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

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

Un mot infini $y$ sur un alphabet $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 $y$ est défini par un triplet $(a,f,h)$, où $a$ est une lettre, $f$ est un morphisme prolongeable en $a$, et $h$ est un morphisme de codage. Le mot infini engendré par ce triplet est

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

Exemples

Premiers exemples

• Le morphisme de Thue-Morse $\mu$ est défini par${\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &ba\end{array}}$.Il est prolongeable à la fois en la lettre $a$ et en la lettre $b$. Pour la lettre $a$, on obtient le mot infini de Thue-Morse :$abbabaabbaababbabaababbaabbabaab\cdots$et pour la lettre $b$, on obtient le mot opposé$baababbaabbabaababbabaabbaababba\cdots$.Ce sont donc des mots purement morphiques.
• Le morphisme de Fibonacci est défini par${\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &a\end{array}}$.Il est prolongeable en $a$ ; en itérant, on obtient le mot infini :$abaababaabaababaababa\cdots$.C'est un mot purement morphique.
• Le morphisme${\begin{array}{rcl}a&\mapsto &a1\\1&\mapsto &001\\0&\mapsto &0\end{array}}$est prolongeable en $a$. En itérant, on obtient le mot infini :$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 $a$ et $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 $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$abcacbabcbacabcacbacabcb\cdots$est à la fois un mot purement morphique, car engendré par le morphisme${\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 $m>1$ un entier, soit $A=\{0,\dots ,m-1\}$, et soit $w\in A^{+}$. La suite de comptage de blocs est le mot infini

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

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

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

la suite d'entiers sur $A$ définie par

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

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

Les auteurs prouvent le résultat suivant :

Si l'entier $m$ est un nombre premier, alors la suite $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 $w$ est une lettre non nulle.

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

Matrice du morphisme générateur

Matrice d'un morphisme : le coefficient en ligne $a$ et colonne $b$ est le nombre $|f(b)|_{a}$ d'occurrences de la lettre $a$ dans le mot $f(b)$.

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

Exemples

Pour la suite de Fibonacci, la matrice est :

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

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

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

pour la suite ternaire de Thue, c'est:

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

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

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

Pour un mot w, on a la formule :

${\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 :

${\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 :

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

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

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

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

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

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

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

Récurrence uniforme

Soit $x$ un mot infini sur un alphabet $A$. Le mot $x$ est uniformément récurrent si, pour tout entier $n$, il existe un entier $R(n)$ tel que tout facteur de longueur $R(n)$ de $x$ contient tous les facteurs de longueur $n$ de $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]}

Propriétés

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 $f$ est non effaçant si $f(b)$ n'est pas le mot vide pour toute lettre $b$.

Complexité des mots morphiques

La fonction de complexité $c_{x}$ d'un mot infini $x$ est la fonction qui, pour tout entier naturel $n$, donne le nombre $c_{x}(n)$ de facteur de $x$ de longueur $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 $x$ un mot infini binaire morphique. La fonction de complexité de $x$ vérifie l'une des propriétés suivantes

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

Problèmes de décision

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

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

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

Variantes

Dans un article publié sur Arxiv, 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 ($1\Rightarrow 2$)
3. Mot purement morphique uniforme : le morphisme sousjacent est uniforme ($3\Rightarrow 1$)
4. Mot morphique uniforme ($4\Rightarrow 2$)
5. Mot purement morphique primitif ($5\Rightarrow 1,6$)
6. Mot morphique primitif: le morphisme est primitif ($6\Rightarrow 2$)
7. Mot purement morphique primitif uniforme ($7\Rightarrow 1,\ldots ,6,8$)
8. Mot morphique primitif uniforme ($8\Rightarrow 2,4,6$)
9. Mot uniformément récurrent ($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.

Notes et 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).
• 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)