Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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
start with proving a martingale characterisation of exact Hausdorff
dimension. Then using semi-computable super-martingales we introduce the
notion of exact constructive dimension ... more >>>

ISSN 1433-8092 | Imprint