Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Hausdorff dimension:
TR01-059 | 20th July 2001
Elvira Mayordomo

A Kolmogorov complexity characterization of constructive Hausdorff dimension

Revisions: 3

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

TR02-011 | 14th October 2001
Boris Ryabko

The nonprobabilistic approach to learning the best prediction.

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

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

Special emphasis is laid on bounds on the complexity of strings in
more >>>

TR08-106 | 12th November 2008
Jack H. Lutz

A Divergence Formula for Randomness and Dimension

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

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

Furthermore, we generalise Ryabko's result on the Hausdorff dimension of the
... 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