__
Revision #1 to TR16-013 | 13th October 2016 14:11
__
#### Bounds on the Kolmogorov complexity function for infinite words

**Abstract:**
The Kolmogorov complexity function of an infinite word $\xi$ maps a natural

number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We

investigate the maximally achievable complexity function if $\xi$ is taken

from a constructively describable set of infinite words. Here we are

interested in linear upper bounds where the slope is the Hausdorff

dimension of the set.

As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets

obtained from constructively describable infinite iterated function

systems. In these cases, for a priori and monotone complexity, the upper

bound coincides (up to an additive constant) with the lower bound, thus

verifying the existence of oscillation-free maximally complex infinite

**Changes to previous version:**
correction of some typos

__
TR16-013 | 12th January 2016 16:54
__

#### Bounds on the Kolmogorov complexity function for infinite words

**Abstract:**
The Kolmogorov complexity function of an infinite word $\xi$ maps a natural

number to the complexity $K(\xi|n)$ of the $n$-length prefix of $\xi$. We

investigate the maximally achievable complexity function if $\xi$ is taken

from a constructively describable set of infinite words. Here we are

interested in linear upper bounds where the slope is the Hausdorff

dimension of the set.

As sets we consider $\Pi_{1}$-definable sets obtained by dilution and sets

obtained from constructively describable infinite iterated function

systems. In these cases, for a priori and monotone complexity, the upper

bound coincides (up to an additive constant) with the lower bound, thus

verifying the existence of oscillation-free maximally complex infinite