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

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éciproquement, on a :

Si un mot morphique est uniformément récurrent, alors il possède un générateur primitif.

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

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[2]

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 [3] :

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 }}$[4].

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

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

• (en) 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)
• (en) 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)
• (en) Fabien Durand, « Dedicability of the HD0L ultimate periodicity problem », arXiv,‎ 2011 (arXiv 1111.3268v1)
• (en) Ivan Mitrofanov, « A proof for the decidability of HD0L ultimate periodicity », arXiv,‎ 2011 (arXiv 1110.4780)
• (en) Ivan Mitrofanov, « On uniform recurrence of HD0L systems », arXiv,‎ 2011 (arXiv 1111.1999v2)