Coût et dimension des mots d'entropie topologique nulle
Cost and dimension of words of zero topological entropy
Anglais
La complexité d'un langage $L$ est définie comme la fonction $p_L (n)$ qui compte pour chaque $ n $ le nombre de mots de longueur $n$ dans $L$. Nous nous intéressons à savoir si $L$ est contenu dans un produit fini de la forme $S^k$, o\`u $S$ est un langage de complexité strictement inférieure. Dans cet article, nous considérons des langages d'entropie topologique nulle, c'est-à-dire $\limsup_ {n \to \infty} \log p_L (n) / n = 0$. Nous définissons l'$\alpha$-dimension d'un langage $L$ comme la borne inférieure des nombres entiers $k$ tels qu'il existe un langage $S$ de complexité $O(n^\alpha)$ avec $L \subseteq S^k$. Nous définissons ensuite le coût $c(L)$ comme la borne inférieure de tous les nombres réels $\alpha$ pour lesquels l'$\alpha$-dimension de $L$ est finie. En particulier, les définitions ci-dessus s'appliquent au langage des facteurs d'un mot infini. Dans l'article, nous cherchons les liens entre la complexité d'un langage (ou d'un mot infini) et sa dimension et son coût, et montrons qu'ils peuvent être assez compliqués.