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 s u b s e t e q A^{*}

defined in terms of the semigroup structure on

A^{*} .

For each

L s u b s e t e q A^{*},

we define its {it cost}

c (L)

as the infimum of all real numbers

a l p h a

for which there exist a language

S s u b s e t e q A^{*}

with

p_{S} (n) = O (n^{a} l p h a)

and a positive integer

k

with

L s u b s e t e q S^{k} .

We also define the {it cost dimension}

d_{c} (L)

as the infimum of the set of all positive integers

k

such that

L s u b s e t e q S^{k}

for some language

S

with

p_{S} (n) = O (n^{c (L)}) .

We are primarily interested in languages

L

given by the set of factors of an infinite word

x = x_{0} x_{1} x_{2} c d o t s i n A^{o} m e g a

of zero topological entropy, in which case

c (L) < + i n f t y .

We establish the following characterisation of words of linear factor complexity: Let

x i n A^{o} m e g a

and

L =

Fac

(x)

be the set of factors of

x .

Then

p_{x} (n) = T h e t a (n)

if and only

c (L) = 0

and

d_{c} (L) = 2.

In other words,

p_{x} (n) = O (n)

if and only if Fac

(x) s u b s e t e q S^{2}

for some language

S s u b s e t e q A^{+}

of bounded complexity (meaning

l i m s u p p_{S} (n) < + i n f t y) .

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

p_{L} (n) = O (l o g n)

(and hence of cost equal to

0)

and of cost dimension

+ i n f t y .

In this paper we investigate the cost and cost dimension of languages defined by infinite words of zero topological entropy.

Recommendations

Cites work

Cited in

(1)

This page was built for publication: Cost and dimension of words of zero topological entropy