Cost and dimension of words of zero topological entropy

Cassaigne, Julien; Frid, Anna E.; Puzynina, Svetlana; Zamboni, Luca Q.

doi:10.24033/bsmf.2794

Geodesic

Parcourir par

Cost and dimension of words of zero topological entropy
[Coût et dimension des mots d’entropie topologique nulle]

Cassaigne, Julien ¹ ; Frid, Anna E.¹ ; Puzynina, Svetlana ² ; Zamboni, Luca Q.³

¹ Aix Marseille Univ, CNRS, Centrale Marseille, I2M, Marseille, France
² Saint Petersburg State University, 7–9 Universitetskaya emb., 199034 Saint Petersburg, Russia and also Sobolev Institute of Mathematics, 4 Acad. Koptyug avenue, 630090 Novosibirsk, Russia
³ Institut Camille Jordan, Université Claude Bernard Lyon 1, 43 boulevard du 11 novembre 1918 F-69622 Villeurbanne Cedex

Bulletin de la Société Mathématique de France, Tome 147 (2019) no. 4, pp. 639-660

Voir la notice de l'article provenant de la source Numdam

Abstract (VO)
Résumé

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 ${lim sup}_{n \to \infty} log p_{L} (n) / n = 0$ . We define the $α$ -dimension of a language $L$ as the infimum of integer numbers $k$ such that there exists a language $S$ of complexity $O (n^{α})$ such that $L \subseteq S^{k}$ . We then define the cost $c (L)$ as the infimum of all real numbers $α$ for which the $α$ -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.

La complexité d’un langage $L$ est définie comme la fonction $p_{L} (n)$ qui compte 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ù $S$ est un langage de complexité strictement inférieure. Dans cet article, nous considérons des langages d’entropie topologique nulle, c’est-à-dire ${lim sup}_{n \to \infty} log p_{L} (n) / n = 0$ . Nous définissons l’ $α$ -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^{α})$ 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 $α$ pour lesquels l’ $α$ -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.

Reçu le : 2018-07-13
Révisé le : 2019-01-14
Accepté le : 2019-02-01
Publié le : 2019-12-04

MR Zbl

DOI : 10.24033/bsmf.2794

Classification : 68R15, 37B10
Keywords: Symbolic dynamics, Factor complexity, Topological entropy
Mots-clés : Dynamique symbolique, Complexité, Entropie topologique

Affiliations des auteurs :

Cassaigne, Julien ¹ ; Frid, Anna E. ¹ ; Puzynina, Svetlana ² ; Zamboni, Luca Q. ³

@article{BSMF_2019__147_4_639_0,
     author = {Cassaigne, Julien and Frid, Anna E. and Puzynina, Svetlana and Zamboni, Luca Q.},
     title = {Cost and dimension of words of zero topological entropy},
     journal = {Bulletin de la Soci\'et\'e Math\'ematique de France},
     pages = {639--660},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {147},
     number = {4},
     year = {2019},
     doi = {10.24033/bsmf.2794},
     mrnumber = {4057713},
     zbl = {1465.68221},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.24033/bsmf.2794/}
}

TY  - JOUR
AU  - Cassaigne, Julien
AU  - Frid, Anna E.
AU  - Puzynina, Svetlana
AU  - Zamboni, Luca Q.
TI  - Cost and dimension of words of zero topological entropy
JO  - Bulletin de la Société Mathématique de France
PY  - 2019
SP  - 639
EP  - 660
VL  - 147
IS  - 4
PB  - Société mathématique de France
UR  - http://geodesic.mathdoc.fr/articles/10.24033/bsmf.2794/
DO  - 10.24033/bsmf.2794
LA  - en
ID  - BSMF_2019__147_4_639_0
ER  -

%0 Journal Article
%A Cassaigne, Julien
%A Frid, Anna E.
%A Puzynina, Svetlana
%A Zamboni, Luca Q.
%T Cost and dimension of words of zero topological entropy
%J Bulletin de la Société Mathématique de France
%D 2019
%P 639-660
%V 147
%N 4
%I Société mathématique de France
%U http://geodesic.mathdoc.fr/articles/10.24033/bsmf.2794/
%R 10.24033/bsmf.2794
%G en
%F BSMF_2019__147_4_639_0

Cassaigne, Julien; Frid, Anna E.; Puzynina, Svetlana; Zamboni, Luca Q. Cost and dimension of words of zero topological entropy. Bulletin de la Société Mathématique de France, Tome 147 (2019) no. 4, pp. 639-660. doi: 10.24033/bsmf.2794

Cité par Sources :