×

zbMATH — the first resource for mathematics

Effective fractal dimensions. (English) Zbl 1058.03044
Summary: Classical fractal dimensions (Hausdorff dimension and packing dimension) have recently been effectivized by (i) characterizing them in terms of real-valued functions called gales, and (ii) imposing computability and complexity constraints on these gales. This paper surveys these developments and their applications in algorithmic information theory and computational complexity theory.

MSC:
03D45 Theory of numerations, effectively presented structures
28A78 Hausdorff and packing measures
68Q30 Algorithmic information theory (Kolmogorov complexity, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D15 Complexity of computation (including implicit computational complexity)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] and Resource-bounded measure and randomness. In: Complexity, Logic and Recursion Theory (A. Sorbi, ed.), pp. 1-47, Lecture Notes in Pure and Applied Mathematics (Marcel Dekker, New York 1997).
[2] and Hausdorff dimension in exponential time. Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 210-217 (2001).
[3] and Effective strong dimension, algorithmic information, and computational complexity. Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science, pp. 632-643 (Springer-Verlag, New York et al. 2004)
[4] and Infinitely-often autoreducible sets. Proceedings of the 14th Annual International Symposium on Algorithms and Computation, pp. 98-107 (2003).
[5] Buhrman, Lecture Notes in Logic 12 pp 45– (1998) · doi:10.1007/978-3-662-22110-5_2
[6] Buhrman, EXP Problem. SIAM J. Computing 30 pp 576– (2001)
[7] Cai, J. Computer and Systems Sciences 49 pp 605– (1994)
[8] Chaitin, J. ACM 22 pp 329– (1975)
[9] Chaitin, Advances in Applied Mathematics 8 pp 119– (1987)
[10] Dai, Theoret. Comp. Sci. 310 pp 1– (2004)
[11] Applications of recursive operators to randomness and complexity. PhD thesis, University of California at Santa Barbara 1998.
[12] Ebert, SIAM J. Computing 32 pp 1542– (2003)
[13] Measure, Topology, and Fractal Geometry (Springer-Verlag, New York et al. 1990).
[14] Fractal Geometry: Mathematical Foundations and Applications (John Wiley & Sons, New York 1990). · Zbl 0689.28003
[15] Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report cs. CC/0208044, Computing Research Repository 2002.
[16] and Prediction and dimension. J. of Computer and System Sciences (to appear). A preliminary version appeared in: Proceedings of the 15th Annual Conference on Computational Learning Theory, pp. 380-395 (2002). · Zbl 1050.68061
[17] Hausdorff, Math. Annalen 79 pp 157– (1919)
[18] Effective Fractal Dimension Bibliography. Available under http://www.cs.uwyo.edu/?jhitchco/bib/dim.html (current July, 2003).
[19] Resource-Bounded Measure Bibliography. Available under http://www.cs.uwyo.edu/?jhitchco/bib/rbm.html (current July, 2003).
[20] Correspondence principles for effective dimensions. Theory of Computing Systems (to appear). A preliminary version appeared in: Proceedings of the 29th International Colloquium on Automata, Languages, and Programming, p. 561-571 (2002).
[21] Hitchcock, Theoret. Comput. Sci. 289 pp 861– (2002)
[22] Hitchcock, Theoret. Comp. Sci. 304 pp 431– (2003)
[23] Hitchcock, Information Processing Letters 86 pp 9– (2003)
[24] Small spans in scaled dimension. In: Proceedings of the 19th IEEE Conference on Computational Complexity 2004. · Zbl 1101.68035
[25] and Scaled dimension and nonuniform complexity. J. Computer and System Sciences (to appear). A preliminary version appeared in: Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, pp. 278-290 (2003). · Zbl 1039.68052
[26] and The arithmetical complexity of dimension and randomness. Proceedings of the 12th Annual Conference of the European Association for Computer Science Logic, pp. 241-254 (Springer-Verlag, New York et al. 2003).
[27] Juedes, SIAM J. Computing 24 pp 279– (1995)
[28] Levin, Soviet Mathematics Doklady 14 pp 1413– (1973)
[29] Levin, Problems of Information Transmission 10 pp 206– (1974)
[30] Théorie de l’Addition des Variables Aleatoires (Gauthier-Villars, Paris 1937 - second edition 1954).
[31] and An Introduction to Kolmogorov Complexity and its Applications (Springer-Verlag, Berlin et al. 1997). · Zbl 0866.68051
[32] Lutz, J. Computer and System Sciences 44 pp 220– (1992)
[33] The quantitative structure of exponential time. In: Complexity Theory Retrospective II (L. A. Hemaspaandra and A. L. Selman, eds.), pp. 225-254 (Springer-Verlag, New York et al. 1997).
[34] Resource-bounded measure. Proceedings of the 13th IEEE Conference on Computational Complexity, 236-248 (1998). · Zbl 0935.68044
[35] Gales and the constructive dimension of individual sequences. Proceedings of the 27th International Colloquium on Automata, Languages, and Programming, 902-913 (2000). Revised as [37]. · Zbl 0973.68087
[36] Lutz, SIAM J. Computing 32 pp 1236– (2003)
[37] A preliminary version appeared in: Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity, 158-169 (2000).
[38] Lutz, Information and Computation 187 pp 49– (2003)
[39] Lutz, Bulletin of the European Association for Theoretical Computer Science 68 pp 64– (1999)
[40] Martin-Löf, Information and Control 9 pp 602– (1966)
[41] Mattila, Mathematical Proceedings of the Cambridge Philosophical Society 121 pp 81– (1997)
[42] Effective Hausdorff dimension. Proceedings of Foundations of the Formal Sciences III, pp. 171-186 (Kluwer Academic Press).
[43] Mayordomo, Information Processing Letters 84 pp 1– (2002)
[44] Hausdorff Measures (Cambridge University Press, Cambridge 1998).
[45] Ryabko, Soviet Mathematics Doklady 30 pp 219– (1984)
[46] Ryabko, Problems of Information Transmission 22 pp 170– (1986) · Zbl 0613.94006
[47] Ryabko, Problems of Information Transmission 29 pp 186– (1993)
[48] Ryabko, Journal of Complexity 10 pp 281– (1994)
[49] Schnorr, Mathematical Systems Theory 5 pp 246– (1971)
[50] Zufälligkeit und Wahrscheinlichkeit (Springer-Verlag, Berlin et al. 1971).
[51] Schnorr, J. Computer and System Sciences 7 pp 376– (1973)
[52] A survey of the theory of random sequences. In: Basic Problems in Methodology and Linguistics (R. E. Butts and J. Hintikka, eds.), pp. 193-210 (D. Reidel, Dordrecht 1977).
[53] Shannon, Bell System Technical J. 28 pp 59– (1949) · doi:10.1002/j.1538-7305.1949.tb03624.x
[54] Shen’, Semiotika i Informatika 18 pp 14– (1982)
[55] Shen’, Soviet Mathematics Doklady 38 pp 316– (1989)
[56] 1975. Reported in [9].
[57] Staiger, Information and Computation 103 pp 159– (1993)
[58] Staiger, Theory of Computing Systems 31 pp 215– (1998) · Zbl 0912.68119
[59] How much can you win when your adversary is handicapped. In: Numbers, Information and Complexity, pp. 403-412 (Kluwer Academic Press, 2000). · Zbl 0955.68058
[60] Constructive dimension equals Kolmogorov complexity. Technical Report CDMTCS-210, University of Auckland, January 2003.
[61] Sullivan, Acta Mathematica 153 pp 259– (1984)
[62] Tadaki, Hokkaido Mathematical Journal 31 pp 219– (2002) · Zbl 0996.68071 · doi:10.14492/hokmj/1350911778
[63] Complexity and randomness. Technical Report CDMTCS-212, University of Auckland, March 2003.
[64] Tricot, Mathematical Proceedings of the Cambridge Philosophical Society 91 pp 57– (1982)
[65] Étude Critique de la Notion de Collectif (Gauthier-Villars, Paris 1939). · Zbl 0021.14505
[66] Zvonkin, Russian Mathematical Surveys 25 pp 83– (1970)
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.