Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > SEARCH:
Results for query Staiger:

TR06-070 | 23rd May 2006
Ludwig Staiger

The Kolmogorov complexity of infinite words

We present a brief survey of results on relations between the Kolmogorov
complexity of infinite strings and several measures of information content
(dimensions) known from dimension theory, information theory or fractal
geometry.

Special emphasis is laid on bounds on the complexity of strings in
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 >>>


TR11-132 | 2nd September 2011
Ludwig Staiger

Oscillation-free Chaitin $h$-random sequences

Revisions: 1

The present paper generalises results by Tadaki [12] and Calude et al. [1] on oscillation-free partially random infinite strings. Moreover, it shows that oscillation-free partial Chaitin randomness can be separated from scillation-free partial strong Martin-L\"of randomness by $\Pi_{1}^{0}$-definable sets of infinite strings.

more >>>

TR11-074 | 27th April 2011
Ludwig Staiger

Exact constructive dimension

Revisions: 1

The present paper generalises results by Lutz and Ryabko. We prove a
martingale characterisation of exact Hausdorff dimension. On this base we
introduce the notion of exact constructive dimension of (sets of) infinite
strings.

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the
... more >>>


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




ISSN 1433-8092 | Imprint