Cost and dimension of words of zero topological entropy

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

doi:10.24033/bsmf.2794

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

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-21

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. ³

¹ 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

@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},
     year = {2019},
     publisher = {Soci\'et\'e math\'ematique de France},
     volume = {147},
     number = {4},
     doi = {10.24033/bsmf.2794},
     mrnumber = {4057713},
     zbl = {1465.68221},
     language = {en},
     url = {https://www.numdam.org/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  - https://www.numdam.org/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 https://www.numdam.org/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

Bibliographie
Cité par

Allouche, J.-P.; Shallit, J. Automatic Sequences, Theory, Applications, Generalizations, Cambridge University Press, 2003 | MR | Zbl | DOI

Cassaigne, J. Special factors of sequences with linear subword complexity, Proceedings of DLT 1995, World Sci. Publishing, Singapore (1996), pp. 25-34 | MR | Zbl

Cassaigne, J.; Frid, A.; Puzynina, S.; Zamboni, L. A characterisation of words of sub-linear complexity, Bull. AMS | Zbl

Cassaigne, J.; Frid, A.; Puzynina, S.; Zamboni, L. Subword complexity and decomposition of the set of factors (LNCS), Proceedings of MFCS 2014, Springer (2014), pp. 147-158 | MR | Zbl

Cassaigne, J.; Nicolas, F. Factor complexity, Combinatorics, Automata and Number Theory (Encyclopedia Math. Appl.), Cambridge Univ. Press (2010), pp. 163-247 | MR | Zbl | DOI

Lothaire, M. Algebraic Combinatorics on Words, Cambridge University Press, 2002 | Zbl | MR | DOI

Morse, M.; Hedlund, G. Symbolic dynamics, Amer. J. Math., Volume 60 (1938), pp. 815-866 | MR | JFM | DOI

Pansiot, J.-J. Complexité des facteurs des mots infinis engendrés par morphismes itérés (LNCS), Proceedings of ICALP 1984, Springer, Heidelberg (1984), pp. 380-389 | MR | Zbl

Cité par Sources :