This paper describes the Lempel-Ziv dimension (Hausdorff like
dimension inspired in the LZ78 parsing), its fundamental properties
and relation with Hausdorff dimension.
It is shown that in the case of individual infinite sequences, the
Lempel-Ziv dimension matches with the asymptotical Lempel-Ziv
compression ratio.
This fact is used to describe results ... more >>>
We define a new discrete version of scaled dimension and we find
connections between the scaled dimension of a string and its Kolmogorov
complexity and predictability. We give a new characterization
of constructive scaled dimension by Kolmogorov complexity, and prove
a new result about scaled dimension and prediction.
Effective fractal dimension was defined by Lutz (2003) in order to quantitatively analyze the structure of complexity classes.
Interesting connections of effective dimension with information theory were also found, in fact the cases of polynomial-space and constructive dimension can be precisely characterized in terms of Kolmogorov complexity, while analogous ...
more >>>
Scaled dimension has been introduced by Hitchcock et al (2003) in order to quantitatively distinguish among classes such as SIZE(2^{a n}) and SIZE(2^{n^{a}}) that have trivial dimension and measure in ESPACE.
more >>>
