SMF

Coût et dimension des mots d'entropie topologique nulle

Cost and dimension of words of zero topological entropy

Julien CASSAIGNE, Anna E. FRID, Svetlana PUZYNINA, Luca Q. ZAMBONI
Coût et dimension des mots d'entropie topologique nulle
  • Consulter un extrait
  • Année : 2019
  • Fascicule : 4
  • Tome : 147
  • Format : Électronique
  • Langue de l'ouvrage :
    Anglais
  • Class. Math. : 68R15, 37B10
  • Pages : 639-660
  • DOI : 10.24033/bsmf.2794

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.

The (factor) complexity of a language $L$ is defined as a function $p_L(n)$ which counts for each $n$ the number of words in $L$ of length  $n$. We are interested in whether $L$ is contained in a finite product of the form $S^k$, where $S$ is a language of strictly lower complexity. In this paper, we focus on languages of zero topological entropy, meaning $\limsup_{n\to \infty} \log p_L(n) /n = 0$. We define the $\alpha$-dimension of a language $L$ as the infimum of integer numbers $k$ such that there exists a language $S$ of complexity $O(n^\alpha)$ such that  $L \subseteq S^k$. We then define the cost $c(L)$ as the infimum of all real numbers $\alpha$ for which the $\alpha$-dimension of $L$ is finite. In particular, the above definitions apply to the language of factors of  an infinite word. In the paper, we search for connections between the complexity of a language (or an infinite word) and its dimension and cost, and show that they can be rather complicated.

Dynamique symbolique, Complexité, Entropie topologique
Symbolic dynamics, Factor complexity, Topological entropy
Prix
Adhérent 14 €
Non-Adhérent 20 €
Quantité
- +