Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR16-013 | 13th October 2016 14:11

Bounds on the Kolmogorov complexity function for infinite words

Revision #1
Authors: Ludwig Staiger
Accepted on: 13th October 2016 14:11
Keywords:

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

Paper:

TR16-013 | 12th January 2016 16:54

Bounds on the Kolmogorov complexity function for infinite words

TR16-013
Authors: Ludwig Staiger
Publication: 1st February 2016 21:03
Keywords:

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

ISSN 1433-8092 | Imprint