Elvira Mayordomo

We obtain the following full characterization of constructive dimension

in terms of algorithmic information content. For every sequence A,

cdim(A)=liminf_n (K(A[0..n-1])/n.

Boris Ryabko

The problem of predicting a sequence $x_1, x_2,.... $ where each $x_i$ belongs

to a finite alphabet $A$ is considered. Each letter $x_{t+1}$ is predicted

using information on the word $x_1, x_2, ...., x_t $ only. We use the game

theoretical interpretation which can be traced to Laplace where there ...
more >>>

Ludwig Staiger

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

Jack H. Lutz

If $S$ is an infinite sequence over a finite alphabet $\Sigma$ and $\beta$ is a probability measure on $\Sigma$, then the {\it dimension} of $ S$ with respect to $\beta$, written $\dim^\beta(S)$, is a constructive version of Billingsley dimension that coincides with the (constructive Hausdorff) dimension $\dim(S)$ when $\beta$ is ... more >>>

Ludwig Staiger

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

Ludwig Staiger

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