zbMATH — the first resource for mathematics

A Kolmogorov complexity characterization of constructive Hausdorff dimension. (English) Zbl 1045.68570

68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
Full Text: DOI
[1] Chaitin, G.J., Algorithmic information theory, (1987), Cambridge University Press New York · Zbl 1013.00525
[2] Falconer, K., The geometry of fractal sets, (1985), Cambridge University Press New York · Zbl 0587.28004
[3] Hausdorff, F., Dimension und äußeres maß, Math. ann., 79, 157-179, (1919) · JFM 46.0292.01
[4] Li, M.; Vitányi, P.M.B., An introduction to Kolmogorov complexity and its applications, (1997), Springer Berlin
[5] Lutz, J.H., Dimension in complexity classes, (), 158-169, Technical Report cs.CC/0203017, ACM Computing Research Repository
[6] Lutz, J.H., Gales and the constructive dimension of individual sequences, (), 902-913 · Zbl 0973.68087
[7] J.H. Lutz, The dimensions of individual strings and sequences, Technical Report cs.CC/0203017, ACM Computing Research Repository, 2002, Submitted
[8] Ryabko, B.Ya., The complexity and effectiveness of prediction problems, J. complexity, 10, 281-295, (1994) · Zbl 0812.68082
[9] Staiger, L., Kolmogorov complexity and Hausdorff dimension, Inform. and comput., 102, 159-194, (1993) · Zbl 0789.68076
[10] Staiger, L., A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory comput. systems, 31, 215-229, (1998) · Zbl 0896.68080
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.