Utilisateur:ManiacParisien/Mots de faible complexité

En informatique théorique, en combinatoire et en mathématique, et spécialement en combinatoire des mots, un mot de faible complexité est un mot infini dont la fonction de complexité est « à croissance lente »; on entend par là une fonction qui croît linéairement, ou polynomialement, en tout cas nettement moins vite qu'une exponentielle. Ce terme générique a été proposé par Gérard Rauzy.

Définition

La fonction de complexité d'un mot fini ou infini $x$ est la fonction $n\mapsto c_{x}(n)$ qui, pour chaque entier $n$, donne le nombre $c_{x}(n)$ de facteurs (ou blocs) de longueur $n$ dans ce mot. On trouve aussi la notation $p_{x}$ pour cette fonction.

Premier exemple: le mot infini

$u=01(10)^{\omega }=01101010\cdots$

a pour complexité $c_{u}(0)=1,c_{u}(1)=2,c_{u}(2)=3$ et $c_{u}(n)=4$ pour $n\geq 3$

Deuxième exemple: le mot infini de ChampernowneChampernowne:

$c=0110111001011101111000\cdots$

Ce mot est obtenu en concaténant les développements binaires des entiers naturels. Pour tout $n$, chacun des $2^{n}$ mots de longueur est facteur de $c$, donc la complexité du mot de Champernowne est $2^{n}$.

L'entropie topologique d'un mot infini $x$ est la limite

$\lim _{n\to \infty }{\frac {1}{n}}\log c_{x}(n)$

Cette limite existe, car en effet on a

$c_{x}(n+m)\leq c_{x}(n)c_{x}(m)$

donc la fonction $\log c_{x}(n)$ est sous-additive et la limite ci-dessus existe par le lemme de Fekete. Les mots de faible complexité sont les mots d'entropie nulle.

Complexité minimale

Pour un mot infini $x$, un résultat dû à Ethan M. Coven et Gustav HedlundGustav Hedlund dit que si $c_{x}(n)\leq n$ pour un entier $n$, alors le mot $x$ est ultimement périodique. Plus précisément, on a:

Théorème (Coven, Hedlund) —  Soit $x$ un mot infini sur un alphabet à $k$ lettres. Les conditions suivantes sont équivalentes:

1. $c_{x}(n)<n+k-1$ pour un entier $n$,
2. $c_{x}(n)=c_{x}(n+1)$ pour un entier $n$,
3. la fonction $n\mapsto c_{x}(n)$ est bornée,
4. le mot $x$ est ultimement périodique.

Les mots infinis apériodiques de complexité minimale sont binaires (sur un alphabet à deux lettres), et ont une fonction de complexité égale à $n+1$. Ce sont les mots sturmiens. Le plus connu des mots sturmiens est le mot de Fibonacci.

Complexité de mots morphiques

Mots morphiques

Un morphisme $f:A^{*}\to A^{*}$ est prolongeable dans une lettre $a$ de $A$ si $a$ est un préfixe propre de $f(a)$, et si de plus, la suite des longueurs de $f^{n}(a)$ tend vers l'infini lorsque $n$ tend vers l'infini.

Si $f:A^{*}\to A^{*}$ est prolongeable en $a$, alors on a, en définissant le mot $u$ par $f(a)=au$, l'expression

$f^{n}(a)=auf(u)\cdots f^{n-1}(u)$

La suite de ces mots converge vers un mot infini

$f^{\omega }(a)=\lim _{n\to \infty }f^{n}(a)$

Ce mot est le mot infini engendré par $f$ en $a$. 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.

Classification des complexités

Le théorème suivant donne une classification des fonctions de complexités pour les mots morphiques.

Théorème (Pansiot) —  Soit $x$ un mot infini purement morphique. La fonction de complexité de $x$ vérifie l'une des propriétés suivantes

1. $c_{x}(n)=\Theta (1)$,
2. $c_{x}(n)=\Theta (n)$,
3. $c_{x}(n)=\Theta (n\log \log n)$,
4. $c_{x}(n)=\Theta (n\log n)$,
5. $c_{x}(n)=\Theta (n^{2})$.

Les fonctions de complexité des mots morphiques ne sont pas encore complètement caractérisées. On sait

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

1. $c_{x}(n)=\Theta (n{\sqrt[{r}]{n}})$,
2. $c_{x}(n)=O(n\log n)$.

Bibliographie

• (en) Julien Cassaigne et François Nicolas, « Factor complexity », dans 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 (ISBN 978-0-521-51597-9), p. 163-247