Name
Abstract | ||
|---|---|---|
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 ->infinity) log p(L)(n)/n = 0. We define the alpha-dimension of a language L as the infimum of integer numbers k such that there exists a language S of complexity O(n(alpha)) such that L subset of S-k. We then define the cost c(L) as the infimum of all real numbers alpha for which the alpha-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. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.24033/bsmf.2794 | BULLETIN DE LA SOCIETE MATHEMATIQUE DE FRANCE |
Keywords | Field | DocType |
Symbolic dynamics,Factor complexity,Topological entropy | Integer,Discrete mathematics,Combinatorics,Factorial,Topological entropy,Infimum and supremum,Free monoid,Semigroup,Real number,Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
147 | 4 | 0037-9484 |
Citations | PageRank | References |
0 | 0.34 | 3 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Julien Cassaigne | 1 | 282 | 40.80 |
| Anna E. Frid | 2 | 106 | 17.54 |
| Svetlana Puzynina | 3 | 50 | 13.13 |
| Luca Q. Zamboni | 4 | 253 | 27.58 |