Aller au contenu

Utilisateur:ManiacParisien/Mots de faible complexité

Une page de Wikipédia, l'encyclopédie libre.

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

La fonction de complexité d'un mot fini ou infini est la fonction qui, pour chaque entier , donne le nombre de facteurs (ou blocs) de longueur dans ce mot. On trouve aussi la notation pour cette fonction.

Premier exemple: le mot infini

a pour complexité et pour

Deuxième exemple: le mot infini de Champernowne:

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

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

Cette limite existe, car en effet on a

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

Pour un mot infini , un résultat dû à Ethan M. Coven et Gustav Hedlund dit que si pour un entier , alors le mot est ultimement périodique. Plus précisément, on a:

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

  1. pour un entier ,
  2. pour un entier ,
  3. la fonction est bornée,
  4. le mot 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 à . Ce sont les mots sturmiens. Le plus connu des mots sturmiens est le mot de Fibonacci.

Complexité de mots morphiques[modifier | modifier le code]

Mots morphiques[modifier | modifier le code]

Un morphisme est prolongeable dans une lettre de si est un préfixe propre de , et si de plus, la suite des longueurs de tend vers l'infini lorsque tend vers l'infini.

Si est prolongeable en , alors on a, en définissant le mot par , l'expression

La suite de ces mots converge vers un mot infini

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

Classification des complexités[modifier | modifier le code]

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

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

  1. ,
  2. ,
  3. ,
  4. ,
  5. .

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

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

  1. ,
  2. .


Bibliographie[modifier | modifier le code]

  • (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 » (no 135), (ISBN 978-0-521-51597-9), p. 163-247Document utilisé pour la rédaction de l’article