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.

more >>>

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

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

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

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

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