Utilisateur:ManiacParisien/Brouillons/Math-10

Mots S-adiques

Un extension considérable de la notion de mot morphique est constituée par le concept de mot S-adique. Ces mots sont construits comme limites de l'itération de plusieurs morphismes, pris dans un ensemble fini $S$. Contrairement aux mots morphiques, les mots S-adiques ne sont plus en nombre dénombrable. Ils permettent notamment de couvrir l'ensemble des mots sturmiens et épisturmiens.

Définition formelle

Soit $A$ un alphabet, et soit $S$ un ensemble fini d'endomorphismes de $A^{*}$. Soient $\sigma =(\sigma _{0},\sigma _{1},\sigma _{2},\ldots$ une suite infinie d'éléments de l'ensemble $S$, et soit $a_{0}a_{1}a_{2}\cdots$ un mot infini sur $A$. Le mot S-adique défini par ces deux mots infinis est le mot

$w=\lim _{n\to \infty }\sigma _{0}\sigma _{1}\cdots \sigma _{n}(a_{n}^{\omega })$

pourvu que cette limite existe et est un mot infini. Quand les morphismes sont non effaçants, on peut remplacer $a_{n}^{\omega }$ par $a_{n}$.

Exemples

Premiers exemples

• Quand tous les morphismes de la suite $\sigma$ sont les mêmes, ou en d'autres termes quand l'ensemble S est un singleton, on retrouve la notion de mot purement morphique. Il en est de même si la suite $\sigma$ est purement périodique.
• Quand la suite $\sigma$ est ultimement périodique, on peut regrouper les morphismes de la pré-période, et ceux de la période, et les remplacer par un seul morphisme obtenu par composition. Donc tout mot morphique est S-adique; en particulier tout mot automatique est S-adique.

Exemples plus élaborés

Soient

$\varphi :{\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &a\end{array}}\qquad$ et $\qquad \mu :{\begin{array}{rcl}a&\mapsto &ab\\b&\mapsto &ba\end{array}}$

les morphismes de Fibonacci et de Prouhet-Thue-Morse respectivement. On peut les composer en itérant chacun une fois de plus; on obtient la suite de mots

$w_{n}=\varphi \mu \varphi ^{2}\mu ^{2}\cdots \varphi ^{n}\mu ^{n}(a)$,

qui commence par

${\begin{array}{rcl}w_{1}&=&aba\\w_{2}&=&abaaababababbbababbabbbabababaaababa\end{array}}$

On peut voir facilement que chaque mot est préfixe du suivant, et donc que la suite converge.

Mots sturmiens

Propriété — Tout mot sturmien est S-adique.

On considère pour cela les 4 morphismes

$r_{0}=(0\to 0,1\to 10)$, $r_{1}=(0\to 01,1\to 1)$, $\ell _{0}=(0\to 01,\to 01)$ et $\ell _{1}=(0\to 10,1\to 1)$.

Tout mot sturmien est de la forme

$x=\lim _{n\to \infty }\ell _{0}^{k_{0}}r_{0}^{k_{1}}\ell _{1}^{k_{2}}r_{1}^{k_{3}}\ell _{0}^{k_{4}}r_{0}^{k_{5}}\cdots \ell _{1}^{k_{4n+2}}r_{1}^{k_{4n+3}}(0^{\omega })$

pour une suite d'indices $k_{0},k_{1},\ldots$ appropriée.

La conjecture S-adique

Conjecture S-adique — Il existe une condition C telle qu'un mot infini x a une complexité en facteurs au plus linéaire si et seulement si x est S-adique pour un ensemble fini S de morphismes et satisfait la condition C.

Il ne suffit pas qu'un mot soit S-adique pour être de complexité linéaire puisqu'il existe de mots purement morphiques de complexité quadratique.

Bibliographie

• Julien Leroy et Gwenäel Richomme, « A Combinatorial Proof of S-adicity for Sequences with Linear Complexity », Integers, vol. 13,‎ 2013 (ISSN 1553-1732, lire en ligne, consulté le 27 septembre 2019).