TY - JOUR

T1 - COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY

AU - Cassaigne, Julien

AU - Frid, Anna E.

AU - Puzynina, Svetlana

AU - Zamboni, Luca Q.

PY - 2019

Y1 - 2019

N2 - 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 L⊆A∗ defined in terms of the semigroup structure on A∗. For each L⊆A∗, we define its {\it cost} c(L) as the infimum of all real numbers α for which there exist a language S⊆A∗ with pS(n)=O(nα) and a positive integer k with L⊆Sk. We also define the {\it cost dimension} dc(L) as the infimum of the set of all positive integers k such that L⊆Sk for some language S with pS(n)=O(nc(L)). We are primarily interested in languages L given by the set of factors of an infinite word x=x0x1x2⋯∈Aω of zero topological entropy, in which case c(L)<+∞. We establish the following characterisation of words of linear factor complexity: Let x∈Aω and L=Fac(x) be the set of factors of x. Then px(n)=Θ(n) if and only c(L)=0 and dc(L)=2. In other words, px(n)=O(n) if and only if Fac(x)⊆S2 for some language S⊆A+ of bounded complexity (meaning limsuppS(n)<+∞). 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 pL(n)=O(logn) (and hence of cost equal to 0) and of cost dimension +∞. In this paper we investigate the cost and cost dimension of languages defined by infinite words of zero topological entropy.

AB - 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 L⊆A∗ defined in terms of the semigroup structure on A∗. For each L⊆A∗, we define its {\it cost} c(L) as the infimum of all real numbers α for which there exist a language S⊆A∗ with pS(n)=O(nα) and a positive integer k with L⊆Sk. We also define the {\it cost dimension} dc(L) as the infimum of the set of all positive integers k such that L⊆Sk for some language S with pS(n)=O(nc(L)). We are primarily interested in languages L given by the set of factors of an infinite word x=x0x1x2⋯∈Aω of zero topological entropy, in which case c(L)<+∞. We establish the following characterisation of words of linear factor complexity: Let x∈Aω and L=Fac(x) be the set of factors of x. Then px(n)=Θ(n) if and only c(L)=0 and dc(L)=2. In other words, px(n)=O(n) if and only if Fac(x)⊆S2 for some language S⊆A+ of bounded complexity (meaning limsuppS(n)<+∞). 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 pL(n)=O(logn) (and hence of cost equal to 0) and of cost dimension +∞. In this paper we investigate the cost and cost dimension of languages defined by infinite words of zero topological entropy.

KW - Factor complexity

KW - Symbolic dynamics

KW - Topological entropy

UR - http://www.scopus.com/inward/record.url?scp=85085746921&partnerID=8YFLogxK

U2 - 10.24033/BSMF.2794

DO - 10.24033/BSMF.2794

M3 - Article

AN - SCOPUS:85085746921

VL - 147

SP - 639

EP - 660

JO - Bulletin de la Societe Mathematique de France

JF - Bulletin de la Societe Mathematique de France

SN - 0037-9484

IS - 4

ER -