Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR16-013 | 7th October 2020 15:24

Bounds on the Kolmogorov complexity function for infinite words

RSS-Feed




Revision #2
Authors: Ludwig Staiger
Accepted on: 7th October 2020 15:24
Downloads: 247
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 words.



Changes to previous version:

Proposition 5 and Equation (13) corrected

some typos corrected


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
Downloads: 751
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
Downloads: 1302
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