Standard

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 journalArticlepeer-review

Harvard

Cassaigne, J, Frid, AE, Puzynina, S & Zamboni, LQ 2019, 'COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY', Bulletin de la Societe Mathematique de France, vol. 147, no. 4, pp. 639-660. https://doi.org/10.24033/BSMF.2794

APA

Cassaigne, J., Frid, A. E., Puzynina, S., & Zamboni, L. Q. (2019). COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY. Bulletin de la Societe Mathematique de France, 147(4), 639-660. https://doi.org/10.24033/BSMF.2794

Vancouver

Cassaigne J, Frid AE, Puzynina S, Zamboni LQ. COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY. Bulletin de la Societe Mathematique de France. 2019;147(4):639-660. https://doi.org/10.24033/BSMF.2794

Author

Cassaigne, Julien ; Frid, Anna E. ; Puzynina, Svetlana ; Zamboni, Luca Q. / COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY. In: Bulletin de la Societe Mathematique de France. 2019 ; Vol. 147, No. 4. pp. 639-660.

BibTeX

@article{dcba8677837a47848623b92e31ae65ae,
title = "COST and DIMENSION of WORDS of ZERO TOPOLOGICAL ENTROPY",
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 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.",
keywords = "Factor complexity, Symbolic dynamics, Topological entropy",
author = "Julien Cassaigne and Frid, {Anna E.} and Svetlana Puzynina and Zamboni, {Luca Q.}",
year = "2019",
doi = "10.24033/BSMF.2794",
language = "English",
volume = "147",
pages = "639--660",
journal = "Bulletin de la Societe Mathematique de France",
issn = "0037-9484",
publisher = "Societe Mathematique de France",
number = "4",

}

RIS

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