Complexité d'un mot
La complexité combinatoire d'un mot ou plus simplement la complexité d'un mot ou d'une suite est un moyen de mesurer, en combinatoire et en mathématique, et spécialement en combinatoire des mots, divers paramètres d'un mot qui expriment combien il est « compliqué ».
La complexité combinatoire est une mesure différente de la complexité algorithmique ou complexité de Kolmogorov. Ici, on considère le plus souvent la complexité en facteurs (en anglais « subword complexity »).
Parmi les mots distingués dans les diverses mesures de complexité combinatoire, il y a ceux dont la complexité est particulièrement basse. 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. Il existe de nombreuses familles de mots infinis, comme les mots automatiques, les mots morphiques, les mots sturmiens et les mots épisturmiens, qui ont une croissance lente en ce sens.
Une application importante de l'étude des mots infinis à croissance lente est à la théorie des nombres : les mots infinis qui représentent le développement d'un nombre sont à croissance lente si le nombre est rationnel ou transcendant, et plus rapide si le nombre est algébrique irrationnel. On dispose ainsi d'un moyen assez général pour construire des nombres transcendants.
La complexité d'un mot fini ou infini peut se mesurer aussi par le nombre de palindromes; on parle alors de complexité palindromique. Ces deux notions de complexité combinatoire sont liées. Encore une autre mesure de complexité est la complexité abélienne d'un mot.
Complexité en facteurs
[modifier | modifier le code]La fonction de complexité ou complexité en facteurs d'un mot fini ou infini est la fonction
qui, pour chaque entier , donne le nombre de facteurs (ou blocs) distincts de longueur dans ce mot. On trouve aussi la notation ou pour la valeur en de cette fonction.
Premier exemple. Le mot infini
- .
Il 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 .
Justification de la terminologie
[modifier | modifier le code]L'entropie topologique d'un mot infini est la limite
Cette limite existe, car 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 :
- pour un entier ,
- pour un entier ,
- la fonction est bornée,
- 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 purement morphiques
[modifier | modifier le code]Le théorème suivant donne une classification des fonctions de complexités pour les mots purement 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
- ,
- ,
- ,
- ,
- .
Exemples
[modifier | modifier le code]Les mots ultimement périodiques sont de complexité ultimement constante.
Le mot de Fibonacci est sturmien et morphique. Il est de complexité linéaire.
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
Sa complexité est en .
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
Sa complexité est .
Un mot de complexité en : le morphisme
engendre, à partir de la lettre , le mot infini :
La suite des exposants des est :. Sa complexité est (ça demande un peu de calcul !).
Mots morphiques
[modifier | modifier le code]Les fonctions de complexité des mots morphiques ne sont pas encore complètement caractérisées en 2010 (voir Cassaigne et Nicolas (2010)). On sait :
Proposition — 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 ,
- .
On sait que pour tout entier , il existe effectivement un mot infini binaire morphique tel que .
Exemple
[modifier | modifier le code]Soit un alphabet à lettres et considérons le morphisme défini par
et soit donné par pour , , et . On voit que
pour des entiers , et on peut prouver que la suite de croît comme d'où l'on peut déduire que .
Complexité et transcendance
[modifier | modifier le code]Il y a un lien étroit entre la transcendance d'un nombre réel et la complexité du mot infini qu'est son développement dans une base donnée. Soit un entier. Pour tout nombre réel avec , il existe un mot infini unique
à éléments dans l'ensemble tel que
avec la condition supplémentaire que ne se termine pas par une infinité de . Par exemple, en base 10, on a
- .
Réciproquement, un développement en base décrit un nombre réel unique. Un nombre réel est rationnel si et seulement si son développement est ultimement périodique.
On note
le nombre de facteurs de longueur du mot infini qui est le développement de en base , en d'autre termes . On dira pour faire vite que c'est la complexité de , au lieu de dire la complexité du développement de . On a alors le théorème suivant
Théorème (Adamczewski, Bugeaud, Luca)[1] — Si est un nombre irrationnel algébrique, alors
- .
La conclusion du théorème dit que la fonction de complexité de croît plus vite que linéairement. La conséquence immédiate de ce théorème est que si , et si est irrationnel, alors est transcendant. Or, il existe de nombreux mots infinis de complexité linéaire, et tous ces mots infinis représentent donc des nombres soit rationnels, soit transcendants.
Par exemple, tous les nombres irrationnels dont le développement est une suite automatique sont transcendants. Tous les nombres dont le développement est un mot sturmien sont transcendants. La même conclusion vaut pour les mots épisturmiens non ultimement périodiques.
Complexité abélienne
[modifier | modifier le code]La complexité abélienne d'un mot fini ou infini est la fonction qui compte le nombre de facteurs de longueur donnée dans ce mot, à permutation de lettres près. C'est une autre mesure de la complexité combinatoire d'une suite.
Exemple. Les 6 facteurs de longueur 6 du mot de Fibonacci sont . Ces facteurs se regroupent, par une permutation des lettres, en deux classes : les quatre mots contenant deux occurrences de , et les deux qui en contiennent trois. La complexité abélienne prend donc la valeur 2.
Mots de complexité abélienne maximale
[modifier | modifier le code]On note la fonction complexité abélienne d'un mot .
- Propriété.- La complexité abélienne d'un mot infini sur lettres vérifie pour tout .
Cette borne est atteinte par la suite de Champernowne par exemple.
Mot de Thue-Morse
[modifier | modifier le code]Le mot de Thue-Morse a la fonction de complexité suivante :
En fait, une sorte de réciproque est vraie aussi[2]: Si un mot infini binaire récurrent a la même fonction de complexité et la même fonction de complexité abélienne que le mot de Thue-Morse, alors il a les mêmes facteurs.
Mots sturmiens
[modifier | modifier le code]Un mot sturmien est un mot infini binaire qui a exactement facteurs de longueur , pour tout entier naturel . L'exemple paradigmatique de mot sturmien est le mot de Fibonacci.
Parmi les nombreuses propriétés des mots sturmiens, on a la caractérisation[2] :
- Propriété.- La complexité abélienne d'un mot sturmien est constante et égale à . Réciproquement, un mot apériodique qui a complexité abélienne constante égale à est sturmien.
Complexité binomiale
[modifier | modifier le code]Deux mots sont dits k-binomialement équivalents lorsqu'ils possèdent les mêmes sous-mots de longueur au plus k avec les mêmes multiplicités. Cette mesure est un raffinement de l'équivalence abélienne et de la congruence de Simon[3]. La complexité k-binomiale d'un mot infini est, pour tout entier , le nombre de classes, pour cette relation d'équivalence, de l'ensemble des facteurs de longueur apparaissant dans [4],[5]. La complexité -binomiale du mot de Thue-Morse, bien que le mot de Thue-Morse soit apériodique, ne prend que deux valeurs[6].
Définition
[modifier | modifier le code]Formellement, deux mots u et v sont k-binomialement équivalents si
pour tout mot de longueur au plus . Dans cette définition,
est le nombre d'occurrences du mot x comme sous-mot de . Les coefficients binomiaux de mots ont des propriétés proches de celles des nombres. Ainsi, on a par exemple :
Exemples
[modifier | modifier le code]Les quatre mots et sont 2-binomialement équivalents. Si est l'un de ces quatre mots, on a en effet les coefficients suivants :
- et .
Ces mots ne sont pas 2-binomialement équivalents. Par exemple, on a
- et .
En effet, dans ce deuxième mot, le sous-mot apparaît en 4 positions :
- .
Pour , l'équivalence binomiale coïncide avec l'équivalence commutative.
On note le fait que et sont -binomialement équivalents. La relation est compatible avec la concaténation :
- implique pour tous mots .
Complexité binomiale du mot de Thue-Morse
[modifier | modifier le code]On note la complexité d'un mot , c'est-à-dire le nombre de facteur de longueur apparaissant dans , et on note ou plus simplement la complexité -binomiale de , c'est-à-dire le nombre classes de sous-mots -équivalents de longueur du mot . Pour le mot de Thue-Morse, on a le résultat suivant :
Théorème — Soit un entier positif. La complexité -binomiale du mot de Thue-Morse a la forme suivante : pour , on a
- ,
et pour , on a :
Ainsi, pour , la complexité -binomiale du mot de Thue-Morse ne prend que 2 valeurs ; de plus, la deuxième valeur est égale à .
Complexité binomiale des mots sturmiens
[modifier | modifier le code]La complexité -binomiale d'un mot sturmien est égale à sa complexité en facteur. Plus précisément, on
Théorème — Soit un entier. La complexité -binomiale d'un mot sturmien est égale à pour tout entier .
Pour , la complexité binomiale est égale à la complexité abélienne, et vaut donc 2. Pour des valeurs plus grandes de k, on montre que deux facteurs distincts de même longueur d'un mot sturmien ne sont jamais -binomialement équivalents[4].
Complexité cyclique
[modifier | modifier le code]Définition
[modifier | modifier le code]La complexité cyclique d’un mot infini est la fonction [7] qui compte le nombre de classes de conjugaison (ou mots circulaires, ou colliers) de facteurs de longueur dans le mot : pour être tout à fait précis : est le nombre de classes de conjugaison que rencontre l’ensemble des facteurs de longueur [8].
Exemple. Les cinq facteurs de longueur 4 du mot de Fibonacci infini sont . Ces facteurs se regroupent, par permutation circulaire, en deux classes : les trois mots forment contenant une seule occurrence de , et les deux qui en contiennent deux. La complexité cyclique prend donc la valeur 2.
On a , où est la complexité abélienne et est la complexité ordinaire. La complexité en facteurs, la complexité abélienne et la complexité cyclique peuvent être vues comme des actions de divers sous-groupes du groupe symétrique sur les indices d’un mot fini, à savoir respectivement le sous-groupe trivial, le groupe symétrique en entier et le sous-groupe cyclique engendré par la permutation (1,2,…,n).
- Théorème : Un mot est ultimement périodique si et seulement si sa complexité cyclique est bornée.
Ceci est l’analogue du théorème de Morse-Hedlund.
Mots sturmiens
[modifier | modifier le code]- Propriété : Soient et deux mots infinis de même complexité cyclique. Si l’un des deux mots est sturmien, alors l’autre l’est également et, à un renommage des lettres près, ils ont même ensemble de facteurs.
La valeur minimale de la fonction de complexité cyclique d’un mot non périodique est 2, car si tous les facteurs de longueur d’un mot sont conjugués, ce mot est périodique. En particulier, si est sturmien, alors , mais ceci ne caractérise pas les mots sturmiens.
Mot de Thue-Morse
[modifier | modifier le code]Pour le mot de Thue-Morse la fonction de complexité cyclique n'est pas bornée : on a ,
Complexité en palindromes
[modifier | modifier le code]Définition
[modifier | modifier le code]La fonction de complexité en palindromes ou complexité palindromique[9] d'un mot fini ou infini est la fonction
qui, pour chaque entier , donne le nombre de facteurs (ou blocs) distincts de longueur dans ce mot qui sont des palindromes. Bien entendu, on a toujours .
Exemple Le mot , préfixe du mot de Prouhet-Thue-Morse a les facteurs 9 palindromes
- ,
et , et .
Exemple Le mot de Fibonacci infini a les facteurs palindromes
- ,
et on peut démontrer que
Cette propriété est caractéristique des mots sturmiens.
Comparaison des deux mesures de complexité
[modifier | modifier le code]Soit un mot infini, et soit sa complexité en palindromes et sa complexité en facteurs. Bien entendu, on a toujours . Il y a une borne bien meilleure[10] :
Cette propriété peut être raffinée dans le cas de mots infinis dont l'ensemble des facteurs est fermé par image miroir, c'est-à-dire tel que pour tout facteur , l'image miroir est encore facteur.
Théorème (Baláži, Masáková, Pelantová)[11],[12] — Soit un mot infini dont l'ensemble des facteurs est fermé par miroir. Pour tout ,
- ,
où ) (resp. ) est le nombre de facteurs (resp. le nombre de facteurs palindromes) de longueur de .
Exemple. Pour tout mot sturmien, on a . Ainsi, le membre droit de l'équation s'évalue en . Il en résulte que . On verra que dans ce cas, on peut remplacer l'inégalité par une égalité. On a donc , donc le nombre de palindromes est alternativement 1 et 2, comme déjà dit plus haut.
Le nombre moyen de facteurs palindromes distincts dans un mot aléatoire de longueur est [13].
Mots riches en palindromes
[modifier | modifier le code]Soit un mot fini, et soit l'ensemble des facteurs de qui sont des palindromes, et soit le nombre d'éléments de . On sait[14] que pour tout mot fini , on a
- .
Un mot est riche en palindromes[15] si l'inégalité est une égalité, donc si
- .
De même, un mot infini est riche en palindromes si tous ses facteurs sont riches en palindromes. Les mots sturmiens, épisturmiens, et plus généralement les mots infinis qui codent des échanges d'intervalles symétriques sont riches. Le mot de Thue-Morse n'est pas riche. Le préfixe de longueur 8 du mot de Thue-Morse et riche puisqu'il a 9 facteurs palindromes. Un examen exhaustif montre que tous les mots binaires de longueur au plus 8 sont riches. Des définitions équivalentes ont été trouvées pour les mots riches :
Théorème — Soit un mot infini. Les conditions suivantes sont équivalentes :
Exemple. Prenons le mot infini de Fibonacci
qui est sturmien donc riche. Prenons par exemple le facteur . Les suffixes palindromes de ce mot sont et . Les deux premiers ont plusieurs occurrences dans w, le troisième, le plus long, n'a qu'une seule occurrence. Le préfixe a trois suffixes palindromes non vides, à savoir , , et . Le dernier est le seul qui est unirécurrent. Pour le facteur 1001, les deux mots de retour complets sont et . Ils sont tous deux palindromes. Enfin, comme , on a pour tout , et d'autre part le mot de Fibonacci a deux facteurs palindromes de longueur paire et un seul de longueur impaire pour toute longueur, donc .
Théorème (Rukavicka)[18] — Soit un mot infini riche en palindromes, sur un alphabet à lettres. Le nombre de facteurs palindromes de longueur dans est majoré par :
- .
Les mêmes arguments donnent aussi une majoration pour le nombre de facteurs d'un mot riche en palindromes :
Théorème (Rukavicka)[18] — Soit un mot infini riche en palindromes, sur un alphabet à lettres. Le nombre de facteurs de longueur dans est majoré par :
- .
On peut se demander[19] comment sont les mots infinis qui ne sont pas riches. On appelle défaut ou défaut palindromique d'un mot le nombre défini par
Ce nombre est toujours positif ou nul. Pour un mot infini , on pose
- .
Ce défaut est nul si le mot est riche. Il est utile, pour simplifier l'énoncé qui suit, de poser
- .
Pour tout mot fini de longueur , on a
- .
La conjecture[20] selon laquelle l'équation
est vraie pour tout mot infini a été prouvée. Le théorème s'énonce comme suit :
Théorème[21] — Soit un mot infini dont l'ensemble des facteurs est fermé par miroir. Alors
- .
Cela signifie aussi que si l'une des deux valeurs ou est infinie, l'autre l'est également.
Mots à défaut positif
[modifier | modifier le code]Le défaut d'un mot peut être nul, positif non nul, ou infini si le mot lui-même est infini. Lorsque le mot a une forme particulière où construit au moyen d'un mécanisme bien connu, on peut donner des indications sur sa complexité en palindromes. Ceci est le cas de mots purement morphiques engendrés par des morphismes primitifs : un morphisme est primitif si sa matrice d'incidence (dont le coefficient d'indice donne le nombre le nombre d'occurrences de la lettre dans le mot ) est primitive. Le morphisme est primitif si et seulement s’il existe un entier tel que toute lettre a une occurrence dans le mot , pour toute lettre de l’alphabet. On considère ici les mots purement morphiques qui sont point fixes d'un morphisme primitif.
Pour le mot de Fibonacci par exemple, on a , et pour le mot de Thue-Morse, . Tous les deux sont des mots purement morphiques points fixes d'un morphisme primitif.
Il existe de mots points fixes de morphismes primitifs de défaut pour tout entier naturel . mais ce sont des mots périodiques. Voici un exemple[22] : soit un entier naturel, et soit
- .
Par exemple . On peut montrer que le mot infini périodique a un défaut palindromique égal à . Ce mot est point fixe du morphisme . Les auteurs de l’article[22] ont formulé la conjecture suivante :
Conjecture (Zero Defect Conjecture ou conjecture du zéro défaut) — Un mot infini qui est point fixe d’un morphisme primitif a un défaut nul ou infini, ou alors il est périodique.
La conjecture est donc que si un mot a un défaut strictement positif et fini, il est périodique. La conjecture est vérifiée dans le cas d’un alphabet binaire[23], mais elle est fausse pour des alphabets plus grands. Un contre-exemple est le mot infini engendré par le morphisme
donné par Michelangelo Bucci et Élise Vaslet[23]. D'autres résultats ont été donnés par Kristina Ago, Bojan Bašić, Stefan Hačko et Danijela Mitrović[24].
Complexité de Lie
[modifier | modifier le code]La complexité de Lie d'un mot infini à droite sur un alphabet est la fonction dont la valeur , pour un entier naturel , est le nombre de classes de conjugaison (pour le décalage cyclique) de facteurs de longueur de avec la propriété que chaque élément de la classe de conjugaison apparaît dans .
Exemples
[modifier | modifier le code]1.- Soit le mot de Thue-Morse, point fixe du morphisme qui envoie 0 sur 01 et 1 sur 10. On a :
Ceci est en accord avec le fait que les seuls carrés dans le mot de Thue-Morse ont longueur ou .
Soit le mot de Fibonacci, point fixe du morphisme qui envoie 0 sur 01 et 1 sur 0. Les nombres de Fibonacci sont définies par et . Alors
Propriétés
[modifier | modifier le code]On note le nombre de facteurs de longueur du mot infini . L'observation principale est la formule suivante :
Théorème — On a .
Pour un mot sturmien qui a la propriété que , le membre droit de l'inégalité est 2.
Il résulte de la formule que la fonction de complexité de Lie est uniformément bornée pour les mots dont la complexité en facteurs est linéaire. Il en résulte aussi comme corollaire que les mots infinis dont la complexité en facteurs est linéaire ont au plus un nombre fini de facteurs primitifs avec la propriété que est à nouveau un facteur pour tout .
On peut montrer que la fonction de complexité de Lie d'une suite -automatique est également -automatique[25].
Les démonstrations de Bell et Shallit sont algébriques, Alessandro De Luca et Gabriele Fici[26] donnent des preuves combinatoires.
Complexité arithmétique
[modifier | modifier le code]La complexité arithmétique d'un mot infini est la fonction qui compte le nombre de mots de longueur donnée composés de lettres apparaissant à des positions en progression arithmétiques (et non seulement consécutives).
C'est une autre mesure de la complexité combinatoire des mots infinis qui est une extension de la complexité en facteurs. Les résultats sont moins spectaculaires que ceux concernant la complexité en facteurs.
Définition et exemples
[modifier | modifier le code]Formellement, étant donné un mot infini
- ,
où les sont des lettres, on appelle clôture arithmétique de l'ensemble
- .
La complexité arithmétique de est la fonction qui à associe le nombre de mots de longueur dans .
Exemples
- Le mot caractéristique des carrés : . Par exemple figure dans sa clôture arithmétique, parce qu'il y a un 1 en positions 1, 25 et 49.
- Le mot de Prouhet-Thue-Morse : . On peut montrer, directement ou comme corollaire du résultat plus général donné plus loin, que , c'est-à-dire que tout mot est dans la clôture arithmétique.
- Le mot de Fibonacci .
Il a été démontré[27] que . Les premières valeurs sont données dans la table suivante[27] :
Propriétés
[modifier | modifier le code]Les résultats généraux sont plus rares que pour la complexité en facteurs.
Mots sturmiens. Pour les mots sturmiens, les résultats sont les suivants[27] :
- La complexité arithmétique d'un mot sturmien est majorée par .
- Pour tout mot sturmien de pente entre et , la complexité est .
Pour les mots sturmiens de pente comprise entre et , il existe une formule explicite, un peu compliquée à expliquer.
Mots symétriques. Une autre catégorie de mots pour lesquels on connaît la complexité arithmétique est celle des mots purement morphiques engendrés par des morphismes symétriques. Un morphisme est symétrique s'il existe une permutation circulaire sur qui commute avec , donc telle que pour toute lettre . L'exemple typique est le morphisme de Thue-Morse, ou le morphisme ternaire associé à la permutation . Les mots de engendrés par des morphismes symétriques sont eux-mêmes appelés des mots symétriques[28]. On a la propriété suivante :
Propriété[28] — Soit un mot symétrique sur un alphabet à lettres. Alors et
- ,
où est un diviseur de .
Voici deux cas particuliers :
- Si est un mot symétrique périodique, alors pour tout .
- Si est symétrique non périodique et si est un nombre premier, alors pour tout . C'est le cas pour le mot de Prouhet-Thue-Morse.
Suites de complexité arithmétique linéaire
[modifier | modifier le code]Quelles sont les suites de faible complexité arithmétique ? Anna Frid[29] a caractérisé les mots infinis de complexité arithmétique linéaire. Pour formuler cette caractérisation, il faut donner quelques définitions. D'abord une notation. Pour un mot infini
où les sont des lettres, on note [30] le mot commençant en et formé des lettres de prises à intervalle , formellement
Par exemple, pour le mot de Prouhet-Thue-Morse
on a . Un mot est dit canoniquement -régulier si est périodique pour tout et tout avec . Par exemple, la suite de Prouhet-Thue-Morse n'est pas canoniquement 2-régulière. En revanche, la suite de pliage de papier
est canoniquement 2-régulière. On peut s'en convaincre pour les petites valeurs de . On a par exemple et . Il reste une définition. Un mot est dans l'orbite d'un mot si l'ensemble des facteurs de est contenu dans l'ensemble des facteurs de [31]. L'énoncé est le suivant
Propriété[29] — Un mot infini uniformément récurrent et non périodique est de complexité arithmétique linéaire si et seulement s'il appartient à l'orbite d'un mot qui est -régulier canonique pour un nombre premier , et vérifie pour deux entiers .
Exemple. Nous avons déjà dit que le mot des pliages est canoniquement 2-régulier. On a de plus , donc la deuxième condition est remplie également.
Dans cet article, A. Frid donne une autre caractérisation des suites de complexité linéaire par des suites dites de Toeplitz d'un type spécifique.
Suites de complexité arithmétique maximale
[modifier | modifier le code]Konieczny et Müllner[32] classifient les suites automatiques sur un alphabet fini avec la propriété que chaque mot sur apparaît dans le long d'une progression arithmétique. Plus généralement, ils obtiennent une formule asymptotique pour la complexité arithmétique (et même polynomiale) des sous-mots d'une séquence automatique donnée.
Complexité non-répétitive
[modifier | modifier le code]La complexité non-répétitive et la complexité non-répétitive initiale sont deux mesures de complexité introduites par T. K. Subrahmonian Moothathu[33], étudiée par Jeremy Nicholson et Narad Rampersad[34], et par Medková, Pelantová et Vandomme[35], et considérées par Yann Bugeaud et Dong Han Kim[36] sous une forme un peu différente. Ces mesures sont liées à l'indice de récurrence et de récurrence initiale dans un mot infini.
Définitions
[modifier | modifier le code]Les notations varient avec les auteurs. Soit un mot infini et un entier.
La complexité non-répétitive initiale est définie par Moothathu comme suit :
- est la longueur du plus court préfixe de qui ne contient pas le début d'une deuxième occurrence du préfixe de longueur .
La complexité non-répétitive est par définition[35] :
- est la longueur du plus court facteur de qui ne contient pas le début d'une deuxième occurrence du préfixe de longueur .
L'indice de récurrence est :
- est la longueur du plus court facteur de qui contient tous les facteurs de longueur .
L'indice de récurrence initiale est :
- est la longueur du plus court préfixe de qui contient tous les facteurs de longueur .
Ces deux dernières mesures sont les contraposées logiques des indices de non-répétivité.
Bugeaud et Kim définissent une fonction notée par :
- est la longueur du plus court préfixe de qui contient deux occurrences (éventuellement chevauchantes) du préfixe de longueur .
Le lien entre ces ceux définitions est donné par la relation :
- .
Les relations entre les valeurs de ces divers indices sont les suivantes[35] :
- .
Exemples
[modifier | modifier le code]Complexite pour Fibonacci m ic r 4 5 9 5 5 10 6 5 11 7 8 15
Pour le mot de Fibonacci , on a
- pour et .
Ici, est le -ième nombre de Fibonacci[36]. Comme on voit sur la table ci-dessus, on a en effet et . La fonction est donc constante entre deux nombres de Fibonacci consécutifs (ajustés).
Pour le mot de Thue-Morse , une formule similaire de constance est vérifiée : on a
- pour .
Propriétés
[modifier | modifier le code]Les mots ultimement périodiques sont caractérisées avec cette nouvelle mesure de complexité comme suit :
Propriété[36] — Les conditions suivantes sont équivalentes :
- est ultimement périodique
- pour tout assez grand
- il existe tel que pour tout .
Les mots sturmiens admettent la caractérisation suivante :
Propriété — Un mot est un mot sturmien si et seulement si pour , avec égalité pour une infinité de .
Une propriété de transcendance
[modifier | modifier le code]Théorème[36] — Soit un mot infini non périodique sur un alphabet fini d'entiers. Si
- ,
alors le nombre réel dont le développement en fraction continue est est transcendant.
Notes et références
[modifier | modifier le code]Références
[modifier | modifier le code]- Adamczewski et Bugeaud 2010, Théorème 8.1.6, page 414.
- Richomme, Saari et Zamboni 2011.
- Marie Lejeune, Michel Rigo et Matthieu Rosenfeld, « The binomial equivalence classes of finite words », Int. J. Algebra Comput., vol. 30, no 7, , p. 1375-1397 (arXiv 2001.11732).
- Michel Rigo et Pavel Salimov, « Another generalization of abelian equivalence: Binomial complexity of infinite words », Theoretical Computer Science, vol. 601, , p. 47–57 (ISSN 0304-3975, DOI 10.1016/j.tcs.2015.07.025)
- Marie Lejeune, Michel Rigo et Matthieu Rosenfeld, « Templates for the k-binomial complexity of the Tribonacci word », Adv. Appl. Math., vol. 112, .
- Marie Lejeune, Julien Leroy et Michel Rigo, « Computing the k-binomial complexity of the Thue–Morse word », Journal of Combinatorial Theory, Series A, vol. 176, , p. 105284 (DOI 10.1016/j.jcta.2020.105284, arXiv 1812.07330).
- Ne pas confondre avec la complexité « ordinaire » qui, dans ce contexte, est notée
- (en) Julien Cassaigne, Gabriele Fici, Marinella Sciortino et Luca Q . Zamboni, « Cyclic complexity of words », Journal of Combinatorial Theory, Series A, vol. 145, , p. 36–56 (ISSN 0097-3165, DOI 10.1016/j.jcta.2016.07.002, arXiv 1402.5843)
- Le terme palindromic complexity apparaît dans l'article Brlek et al. 2004.
- Allouche et al. 2003.
- (en) Peter Baláži, Zuzana Masáková et Edita Pelantová, « Factor versus palindromic complexity of uniformly recurrent infinite words », Theoretical Computer Science, vol. 380, no 3, , p. 266-275 (ISSN 0304-3975, lire en ligne)
- L'énoncé original demande que le mot soit uniformément récurrent. Comme il est observé par Brlek et Reutenauer 2011, l’uniforme récurrence n'est pas utilisée dans la preuve, et il suffit de demander que l'ensemble des facteurs est fermé par miroir.
- Mikhail Rubinchik et Arseny M. Shur, « The number of distinct subpalindromes in random words », Fundamenta Informaticae, vol. 145, no 3, , p. 371–384 (DOI 10.3233/FI-2016-1366).
- C'est un théorème qui apparaît pour la première fois dans : (en) Xavier Droubay, Jacques Justin et Giuseppe Pirillo, « Episturmian words and some constructions of de Luca and Rauzy », Theoretical Computer Science, vol. 255, nos 1-2, , p. 539-553 (DOI 10.1016/S0304-3975(99)00320-5, lire en ligne)
- On trouve aussi la terminologie mot plein, notamment dans l'article de Brlek et al. 2004.
- Un mot est unioccurrent dans un mot s'il a une unique occurrence dans .
- Un mot de retour complet d'un facteur dans est un mot qui a comme préfixe et comme suffixe propre et qui n'a que ces deux occurrences de .
- Josef Rukavicka, « Upper bound for palindromic and factor complexity of rich words », RAIRO - Theoretical Informatics and Applications, vol. 55, , article no 1 (ISSN 0988-3754, DOI 10.1051/ita/2020008, arXiv 1810.03573)
- L'article Brlek et Reutenauer 2011 pose ce problème.
- Conjecture énoncée dans l'article Brlek et Reutenauer 2011.
- (en) Ľubomíra Balková, Edita Pelantová et Štěpán Starosta, « Proof of the Brlek–Reutenauer conjecture” », Theoretical Computer Science, vol. 475, , p. 120-125 (ISSN 0304-3975, DOI 10.1016/j.tcs.2012.12.024)
- Brlek et al. 2004.
- (en) Sébastien Labbé, Edita Pelantová et Štěpán Starosta, « On the Zero Defect Conjecture », European Journal of Combinatorics, vol. 62, , p. 132–146 (ISSN 0195-6698, DOI 10.1016/j.ejc.2016.12.006).
- Kristina Ago, Bojan Bašić, Stefan Hačko et Danijela Mitrović, « On generalized highly potential words », Theoretical Computer Science, vol. 849, , p. 184–196 (ISSN 0304-3975, DOI 10.1016/j.tcs.2020.10.022).
- Bell et Shallit 2022.
- De Luca et Fici 2022.
- (en) Julien Cassaigne et Anna E. Frid, « On the arithmetical complexity of Sturmian words », Theoretical Computer Science, vol. 380, no 3, , p. 304-316 (ISSN 0304-3975, DOI 10.1016/j.tcs.2007.03.022).
- (en) Anna E. Frid, « Arithmetical complexity of the symmetric D0L words », Theoretical Computer Science, vol. 306, , p. 535-542 (DOI 10.1016/S0304-3975(03)00345-1).
- (en) Anna E. Frid, « Sequences of linear arithmetical complexity », Theoretical Computer Science, vol. 339, , p. 68-87 (DOI 10.1016/j.tcs.2005.01.009).
- Frid note ce mot , mais cela rend la lecture bien difficile.
- C'est la version la plus simple de l'assertion que appartient au système dynamique engendré par , c'est-à-dire à la fermeture, pour la topologie sur les suites infinies, de l'ensemble des décalés du mot .
- Jakub Konieczny et Clemens Müllner, « Arithmetical subword complexity of automatic sequences », Arxiv, (DOI 10.48550/arXiv.2309.03180, lire en ligne, consulté le ).
- T.K. Subrahmonian Moothathu, « Eulerian entropy and non-repetitive subword complexity », Theoretical Computer Science, vol. 420, , p. 80–88 (DOI 10.1016/j.tcs.2011.11.013)
- Jeremy Nicholson et Narad Rampersad, « Initial non-repetitive complexity of infinite words », Discrete Applied Mathematics, vol. 208, , p. 114–122 (DOI 10.1016/j.dam.2016.03.010)
- Kateřina Medková, Edita Pelantová et Élise Vandomme, « On non-repetitive complexity of Arnoux–Rauzy words », Discrete Applied Mathematics, vol. 285, , p. 423–433 (DOI 10.1016/j.dam.2020.06.016)
- Yann Bugeaud et Dong Han Kim, « A new complexity function, repetitions in Sturmian words, and irrationality exponents of Sturmian numbers », Trans. Amer. Math. Soc., vol. 371, , p. 3281-3308 (arXiv 1510.00279).
Bibliographie
[modifier | modifier le code]- (en) Jean-Paul Allouche, Michael Baake, Julien Cassaigne et David Damanik, « Palindromic complexity », Theoretical Computer Science, vol. 292, no 1, , p. 9-31 (ISSN 0304-3975, DOI 10.1016/S0304-3975(01)00212-2, lire en ligne)
- (en) Boris Adamczewski et Yves Bugeaud, « Transcendence and Diophantine approximation », 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. 410-451
- (en) Srecko Brlek et Christophe Reutenauer, « Complexity and palindromic defect of infinite words », Theoretical Computer Science, vol. 412, nos 4-5, , p. 493-497 (DOI 10.1016/j.tcs.2010.11.025, lire en ligne)
- (en) Srecko Brlek, Sylvie Hamel, Maurice Nivat et Christophe Reutenauer, « On the palindromic complexity of infinite words », International Journal of Foundations of Computer Science, vol. 15, no 2, , p. 293-306 (DOI 10.1142/S012905410400242X).
- (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-247
- (en) Gwenaël Richomme, Kalle Saari et Luca Q. Zamboni, « Abelian Complexity of minimal subshifts », Journal of the London Mathematical Society, vol. 83, no 1, , p. 79-95 (DOI 10.1112/jlms/jdq063).
- (en) Jason P. Bell et Jeffrey Shallit, « Lie complexity of words », Theoretical Computer Science, vol. 927, , p. 98–108 (DOI 10.1016/j.tcs.2022.06.001, arXiv 2102.03821)
- Alessandro De Luca et Gabriele Fici, « On the Lie complexity of Sturmian words », Theoretical Computer Science, vol. 938, , p. 81–85 (DOI 10.1016/j.tcs.2022.10.009, arXiv 2206.00995).
- Julien Cassaigne, France Gheeraert, Antonio Restivo et Giuseppe Romana, « New string attractor-based complexities for infinite words », Journal of Combinatorial Theory, Series A, vol. 208, , article no 105936 (DOI 10.1016/j.jcta.2024.105936, lire en ligne , consulté le )