Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > A PRIORI COMPLEXITY:
Reports tagged with a priori complexity:
TR16-013 | 12th January 2016
Ludwig Staiger

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

Revisions: 1

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

TR16-139 | 8th September 2016
Ludwig Staiger

#### Exact constructive and computable dimensions

Revisions: 1

In this paper we derive several results which generalise the constructive
dimension of (sets of) infinite strings to the case of exact dimension. We