Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KOLMOGOROV COMPLEXITY FUNCTION:
Reports tagged with Kolmogorov complexity function:
TR16-013 | 12th January 2016
Ludwig Staiger

Bounds on the Kolmogorov complexity function for infinite words

Revisions: 2

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 ... more >>>




ISSN 1433-8092 | Imprint