Complexity and fractal dimensions for infinite sequences with positive entropy

The complexity function of an infinite word w on a finite alphabet A is the sequence counting, for each non-negative n, the number of words of length n on the alphabet A that are factors of the infinite word w. The goal of this work is to estimate the number of words of length n on the alphabet A that are factors of an infinite word w with a complexity function bounded by a given function f with exponential growth and to describe the combinatorial structure of such sets of infinite words. We introduce a real parameter, the word entropy E-W(f) associated to a given function f and we determine the fractal dimensions of sets of infinite sequences with complexity function bounded by f in terms of its word entropy. We present a combinatorial proof of the fact that E-W(f) is equal to the topological entropy of the subshift of infinite words whose complexity is bounded by f and we give several examples showing that even under strong conditions on f, the word entropy E-W(f) can be strictly smaller than the limiting lower exponential growth rate of f.