Research output: Contribution to journal › Article › peer-review
COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY. / Cassaigne, Julien; Frid, Anna E.; Puzynina, Svetlana; Zamboni, Luca Q.
In: Bulletin de la Societe Mathematique de France, Vol. 147, No. 4, 2019, p. 639-660.Research output: Contribution to journal › Article › peer-review
}
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 -
ID: 52532700