Utilisateur:ManiacParisien/Brouillons/Math-10

Mots S-adiques[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

Premiers exemples[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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.

Notes et références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

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