Cost and dimension of words of zero topological entropy

DOI10.24033/BSMF.2794zbMATH Open1465.68221arXiv1607.04728OpenAlexW2500922970MaRDI QIDQ3299253FDOQ3299253

Authors: Julien Cassaigne, Svetlana Puzynina, Luca Q. Zamboni, Anna Frid 

Publication date: 22 July 2020

Published in: Bulletin de la Société mathématique de France (Search for Journal in Brave)

Abstract: Let $A^{*}$ denote the free monoid generated by a finite nonempty set $A.$ In this paper we introduce a new measure of complexity of languages $Lsubseteq{A}^{*}$ defined in terms of the semigroup structure on $A^{*}.$ For each $Lsubseteq{A}^{*},$ we define its {it cost} $c(L)$ as the infimum of all real numbers $alpha$ for which there exist a language $Ssubseteq{A}^{*}$ with $p_S(n)=O(n^{a}lpha)$ and a positive integer $k$ with $Lsubseteq{S}^k.$ We also define the {it cost dimension} $d_c(L)$ as the infimum of the set of all positive integers $k$ such that $Lsubseteq{S}^k$ for some language $S$ with $p_S(n)=O(n^{c(L)}).$ We are primarily interested in languages $L$ given by the set of factors of an infinite word $x=x_0{x}_1{x}_{2}cdotsin{A}^{o}mega$ of zero topological entropy, in which case $c(L)<+infty.$ We establish the following characterisation of words of linear factor complexity: Let $xin{A}^{o}mega$ and $L=$Fac$(x)$ be the set of factors of $x.$ Then $p_x(n)=Theta(n)$ if and only $c(L)=0$ and $d_c(L)=2.$ In other words, $p_x(n)=O(n)$ if and only if Fac$(x)subseteq{S}^2$ for some language $Ssubseteq{A}^{+}$ of bounded complexity (meaning $limsup{p}_S(n)<+infty).$ In general the cost of a language $L$ reflects deeply the underlying combinatorial structure induced by the semigroup structure on $A^{*}.$ For example, in contrast to the above characterisation of languages generated by words of sub-linear complexity, there exist non factorial languages $L$ of complexity $p_L(n)=O(logn)$ (and hence of cost equal to $0)$ and of cost dimension $+infty.$ In this paper we investigate the cost and cost dimension of languages defined by infinite words of zero topological entropy.

Full work available at URL: https://arxiv.org/abs/1607.04728

Recommendations

• Topological entropy of formal languages
• The word entropy and how to compute it
• Complexity and fractal dimensions for infinite sequences with positive entropy
• Complexity of infinite sequences with zero entropy
• Dimension of sequences of low complexity

zbMATH Keywords

symbolic dynamicstopological entropyfactor complexity

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Symbolic dynamics (37B10) Topological entropy (37B40) Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Automatic Sequences
• Title not available (Why is that?)
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Title not available (Why is that?)
• Subword Complexity and Decomposition of the Set of Factors

This page was built for publication: Cost and dimension of words of zero topological entropy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3299253)