Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Constructive dimension and Hausdorff dimension: the case of exact dimension

RSS-Feed




Revision #1
Authors: Ludwig Staiger
Accepted on: 6th January 2016 13:36
Downloads: 646
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
Downloads: 3287
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