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

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.

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

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

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[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.

Renforcement des hypothèses

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

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

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

il existe un entier $r\geq 1$ tel que $c_{x}(n)=\Theta (n{\sqrt[{r}]{n}})$ ,
$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 }$ [4].

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

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

Notes et références

Références

Allouche & Shallit (2003), p. 233, Théorème 7.7.4. Dans le cadre des problèmes de décision dont il est question plus bas, on a besoin d'une preuve constructive de ce fait, donnée dans Durand (2011).
Allouche & Shallit (2003), p. 231, Théorème 7.7.1.
Julien Cassaigne et François Nicolas, « Factor complexity », dans CANT (2010), p. 163-247.
Durand (2011) et Mitrofanov (2011).
Voir Durand (2011) pour un historique.
Mitrofanov (2011).

Bibliographie

(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)

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

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[1] Allouche & Shallit (2003), p. 233, Théorème 7.7.4. Dans le cadre des problèmes de décision dont il est question plus bas, on a besoin d'une preuve constructive de ce fait, donnée dans Durand (2011).

[2] Allouche & Shallit (2003), p. 231, Théorème 7.7.1.

[3] Julien Cassaigne et François Nicolas, « Factor complexity », dans CANT (2010), p. 163-247.

[4] Durand (2011) et Mitrofanov (2011).

[5] Voir Durand (2011) pour un historique.

[6] Mitrofanov (2011).