John Hitchcock, Jack H. Lutz, Sebastiaan Terwijn

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... 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 >>>

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