Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > INFINITE WORD:
Reports tagged with infinite word:
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