Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR11-074 | 6th January 2016 13:36

Constructive dimension and Hausdorff dimension: the case of exact dimension

Revision #1
Authors: Ludwig Staiger
Accepted on: 6th January 2016 13:36
Keywords:

Abstract:

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
set of strings having asymptotic Kolmogorov complexity $\le\alpha$ to the
case of exact dimension.

Paper:

TR11-074 | 27th April 2011 18:06

Exact constructive dimension

TR11-074
Authors: Ludwig Staiger
Publication: 5th May 2011 01:39
Keywords:

Abstract:

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
set of strings having asymptotic Kolmogorov complexity $\le\alpha$ to the
case of exact dimension.

ISSN 1433-8092 | Imprint