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 un alphabet. Un morphisme de monoïdes est prolongeable pour une lettre de si est un préfixe propre de , et si de plus, la suite des longueurs de itérés tend vers l'infini lorsque tend vers l'infini.
Si est prolongeable en , il existe un mot non vide tel que . En itérant, on obtient l'expression :
La suite de ces mots converge vers un mot infini noté :
- .
Ce mot est le mot infini engendré par en . Le morphisme est parfois appelé un générateur du mot infini.
Mot morphique
Un mot infini sur un alphabet est purement morphique s'il existe un morphisme et une lettre dans tel que
- .
Un mot infini sur un alphabet 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 est défini par un triplet , où est une lettre, est un morphisme prolongeable en , et est un morphisme de codage. Le mot infini engendré par ce triplet est
- .
Exemples
- Le morphisme de Thue-Morse est défini par.Il est prolongeable à la fois en la lettre et en la lettre . Pour la lettre , on obtient le mot infini de Thue-Morse :et pour la lettre , on obtient le mot opposé.Ce sont donc des mots purement morphiques.
- Le morphisme de Fibonacci est défini par.Il est prolongeable en ; en itérant, on obtient le mot infini :.C'est un mot purement morphique.
- Le morphismeest prolongeable en . En itérant, on obtient le mot infini :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 et , 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 ). 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-Morseest à la fois un mot purement morphique, car engendré par le morphismeet une suite automatique, par la construction de Thue-Morse.
Matrice du morphisme générateur
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a4/Matrice_de_morphisme.png/220px-Matrice_de_morphisme.png)
À uu morphisme est naturellement associé une -matrice , où est le nombre d'occurrences de la lettre dans le mot . Cette matrice est appelée la matrice d'incidence du morphisme .
Exemples
Pour la suite de Fibonacci, la matrice est :
- ,
pour la suite binaire de Thue-Morse, c'est :
- ,
pour la suite ternaire de Thue, c'est:
- ,
pour la suite de carrés, la matrice est :
- .
Pour un mot w, on a la formule :
et par itération :
et aussi :
Morphisme irréductible et morphisme primitif
Une matrice à coefficients positifs ou nuls est primitive s'il existe un entier telle que les coefficients de la matrice sont tous non nuls. Si est primitive, un tel entier existe vérifiant , où est l'ordre de la matrice .
Un morphisme est primitif si sa matrice d'incidence est primitive. Seule la matrice du dernier exemple n'est pas primitive.
Dire que est primitif revient à dire que pour un certain entier , tous les mots , pour parcourant l'alphabet , contient chacun toutes les lettres de l'alphabet au moins une fois. Par exemple, pour le morphisme ternaire de Thue
on a .
Un matrice d'ordre est irréductible si le graphe dont les arcs sont les couples tels que est fortement connexe.
Si est prolongeable en une lettre de , et si est irréductible, alors (et donc ) est primitive. En effet, soient et deux lettre de . Il existe, dans le graphe dont est la matrice d'adjacence, un chemin de vers , et un chemin de vers , tous deux de longueur au plus . En parcourant une ou plusieurs fois, si nécessaire, la boucle autour de , on obtient un chemin de longueur de vers . Ceci montre que a toutes ses coordonnées non nulles.
Récurrence uniforme
Soit un mot infini sur un alphabet . Le mot est uniformément récurrent si, pour tout entier , il existe un entier tel que tout facteur de longueur de contient tous les facteurs de longueur de .
- 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 une 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 est non effaçant si n'est pas le mot vide pour toute lettre .
Complexité des mots morphiques
La fonction de complexité d'un mot infini est la fonction qui, pour tout entier naturel , donne le nombre de facteur de de longueur . 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 un mot infini binaire morphique. La fonction de complexité de vérifie l'une des propriétés suivantes
- il existe un entier tel que ,
- .
Problèmes de décision
- Il est décidable si un mot morphique est ultimement périodique, c'est-à-dire s'il existe des mots et tels que [4].
Ce résultat était connu depuis longtemps pour les mots purement morphiques[5].
- Il est décidable si un mot morphique 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 » (no 17), , 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, , 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 » (no 135), , 615 p. (ISBN 978-0-521-51597-9, lire en ligne)
- (en) Fabien Durand, « Dedicability of the HD0L ultimate periodicity problem », arXiv, (arXiv 1111.3268v1)
- (en) Ivan Mitrofanov, « A proof for the decidability of HD0L ultimate periodicity », arXiv, (arXiv 1110.4780)
- (en) Ivan Mitrofanov, « On uniform recurrence of HD0L systems », arXiv, (arXiv 1111.1999v2)