Nondeterministic automatic complexity of overlap-free and almost square-free words

Abstract: Shallit and Wang studied deterministic automatic complexity of words. They showed that the automatic Hausdorff dimension

I (m a t h b f t)

of the infinite Thue word satisfies

1 / 3 l e I (m a t h b f t) l e 2 / 3

. We improve that result by showing that

I (m a t h b f t) g e 1 / 2

. For nondeterministic automatic complexity we show

I (m a t h b f t) = 1 / 2

. We prove that such complexity

A_{N}

of a word

x

of length

n

satisfies

A_{N} (x) l e b (n) := l f l o o r n / 2 f l o o r + 1

. This enables us to define the complexity deficiency

D (x) = b (n) - A_{N} (x)

. If

x

is square-free then

D (x) = 0

. If

x

almost square-free in the sense of Fraenkel and Simpson, or if

x

is a strongly cube-free binary word such as the infinite Thue word, then

D (x) l e 1

. On the other hand, there is no constant upper bound on

D

for strongly cube-free words in a ternary alphabet, nor for cube-free words in a binary alphabet. The decision problem whether

D (x) g e d

for given

x

,

d

belongs to

N P c a p E

.

Full work available at URL: https://arxiv.org/abs/1402.3856

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

Cited In (10)

This page was built for publication: Nondeterministic automatic complexity of overlap-free and almost square-free words