{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T22:54:49Z","timestamp":1762296889080,"version":"3.32.0"},"reference-count":66,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T00:00:00Z","timestamp":1101340800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mathematical Logic Qtrly"],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Classical fractal dimensions (Hausdorff dimension and packing dimension) have recently been effectivized by (i) characterizing them in terms of real\u2010valued 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. (\u00a9 2004 WILEY\u2010VCH Verlag GmbH &amp; Co. KGaA, Weinheim)<\/jats:p>","DOI":"10.1002\/malq.200310127","type":"journal-article","created":{"date-parts":[[2004,11,25]],"date-time":"2004-11-25T08:46:46Z","timestamp":1101372406000},"page":"62-72","source":"Crossref","is-referenced-by-count":28,"title":["Effective fractal dimensions"],"prefix":"10.1002","volume":"51","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2004,11,25]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"K.Ambos\u2010Spies andE.Mayordomo Resource\u2010bounded measure and randomness. In: Complexity Logic and Recursion Theory (A. Sorbi ed.) pp. 1\u201347 Lecture Notes in Pure and Applied Mathematics (Marcel Dekker New York 1997).","DOI":"10.1201\/9780429187490-1"},{"key":"e_1_2_1_3_2","doi-asserted-by":"crossref","unstructured":"K.Ambos\u2010Spies W.Merkle J.Reimann andF.Stephan Hausdorff dimension in exponential time. Proceedings of the 16th IEEE Conference on Computational Complexity pp. 210\u2013217 (2001).","DOI":"10.1109\/CCC.2001.933888"},{"key":"e_1_2_1_4_2","doi-asserted-by":"crossref","unstructured":"K. B.Athreya J. M.Hitchcock J. H.Lutz andE.Mayordomo Effective strong dimension algorithmic information and computational complexity. Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science pp. 632\u2013643 (Springer\u2010Verlag New York et al. 2004)","DOI":"10.1007\/978-3-540-24749-4_55"},{"key":"e_1_2_1_5_2","doi-asserted-by":"crossref","unstructured":"R.Beigel L.Fortnow andF.Stephan Infinitely\u2010often autoreducible sets. Proceedings of the 14th Annual International Symposium on Algorithms and Computation pp. 98\u2013107 (2003).","DOI":"10.1007\/978-3-540-24587-2_12"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-22110-5_2"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798343891"},{"key":"e_1_2_1_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80073-X"},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/321892.321894"},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(87)90010-8"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00244-5"},{"key":"e_1_2_1_12_2","unstructured":"T.Ebert Applications of recursive operators to randomness and complexity. PhD thesis University of California at Santa Barbara 1998."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702415317"},{"key":"e_1_2_1_14_2","doi-asserted-by":"crossref","unstructured":"G. A.Edgar Measure Topology and Fractal Geometry (Springer\u2010Verlag New York et al. 1990).","DOI":"10.1007\/978-1-4757-4134-6"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"K.Falconer Fractal Geometry: Mathematical Foundations and Applications (John Wiley & Sons New York 1990).","DOI":"10.2307\/2532125"},{"key":"e_1_2_1_16_2","unstructured":"S. A.Fenner Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report cs. CC\/0208044 Computing Research Repository 2002."},{"key":"e_1_2_1_17_2","doi-asserted-by":"crossref","unstructured":"L.Fortnow andJ. H.Lutz 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\u2013395 (2002).","DOI":"10.1007\/3-540-45435-7_26"},{"key":"e_1_2_1_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01457179"},{"key":"e_1_2_1_19_2","unstructured":"J. M.Hitchcock Effective Fractal Dimension Bibliography. Available under http:\/\/www.cs.uwyo.edu\/\u223cjhitchco\/bib\/dim.html (current July 2003)."},{"key":"e_1_2_1_20_2","unstructured":"J. M.Hitchcock Resource\u2010Bounded Measure Bibliography. Available under http:\/\/www.cs.uwyo.edu\/\u223cjhitchco\/bib\/rbm.html (current July 2003)."},{"key":"e_1_2_1_21_2","doi-asserted-by":"crossref","unstructured":"J. M.Hitchcock 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\u2013571 (2002).","DOI":"10.1007\/3-540-45465-9_48"},{"key":"e_1_2_1_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00340-1"},{"key":"e_1_2_1_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(03)00138-5"},{"key":"e_1_2_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00454-4"},{"key":"e_1_2_1_25_2","unstructured":"J. M.Hitchcock Small spans in scaled dimension. In: Proceedings of the 19th IEEE Conference on Computational Complexity 2004."},{"key":"e_1_2_1_26_2","doi-asserted-by":"crossref","unstructured":"J. M.Hitchcock J. H.Lutz andE.Mayordomo 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\u2013290 (2003).","DOI":"10.1007\/3-540-45061-0_24"},{"key":"e_1_2_1_27_2","doi-asserted-by":"crossref","unstructured":"J. M.Hitchcock J. H.Lutz andS. A.Terwijn The arithmetical complexity of dimension and randomness. Proceedings of the 12th Annual Conference of the European Association for Computer Science Logic pp. 241\u2013254 (Springer\u2010Verlag New York et al. 2003).","DOI":"10.1007\/978-3-540-45220-1_21"},{"key":"e_1_2_1_28_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792238133"},{"key":"e_1_2_1_29_2","first-page":"1413","article-title":"On the notion of a random sequence","volume":"14","author":"Levin L. A.","year":"1973","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_30_2","first-page":"206","article-title":"Laws of information conservation (nongrowth) and aspects of the foundation of probability theory","volume":"10","author":"Levin L. A.","year":"1974","journal-title":"Problems of Information Transmission"},{"key":"e_1_2_1_31_2","unstructured":"P.L\u00e9vy Th\u00e9orie de l'Addition des Variables Aleatoires (Gauthier\u2010Villars Paris 1937 \u2013 second edition 1954)."},{"key":"e_1_2_1_32_2","doi-asserted-by":"crossref","unstructured":"M.Li andP. M. B.Vit\u00e1nyi An Introduction to Kolmogorov Complexity and its Applications (Springer\u2010Verlag Berlin et al. 1997).","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"e_1_2_1_33_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90020-J"},{"key":"e_1_2_1_34_2","doi-asserted-by":"crossref","unstructured":"J. H.Lutz The quantitative structure of exponential time. In: Complexity Theory Retrospective II (L. A. Hemaspaandra and A. L. Selman eds.) pp. 225\u2013254 (Springer\u2010Verlag New York et al. 1997).","DOI":"10.1007\/978-1-4612-1872-2_10"},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","unstructured":"J. H.Lutz Resource\u2010bounded measure. Proceedings of the 13th IEEE Conference on Computational Complexity 236\u2013248 (1998).","DOI":"10.1109\/CCC.1998.694611"},{"key":"e_1_2_1_36_2","doi-asserted-by":"crossref","unstructured":"J. H.Lutz Gales and the constructive dimension of individual sequences. Proceedings of the 27th International Colloquium on Automata Languages and Programming 902\u2013913 (2000). Revised as [37].","DOI":"10.1007\/3-540-45022-X_76"},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701417723"},{"key":"e_1_2_1_37_3","unstructured":"A preliminary version appeared in: Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity 158\u2013169 (2000)."},{"key":"e_1_2_1_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"e_1_2_1_39_2","first-page":"64","article-title":"Twelve problems in resource\u2010bounded measure","volume":"68","author":"Lutz J. H.","year":"1999","journal-title":"Bulletin of the European Association for Theoretical Computer Science"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(66)80018-9"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004196001089"},{"key":"e_1_2_1_42_2","unstructured":"E.Mayordomo Effective Hausdorff dimension. Proceedings of Foundations of the Formal Sciences III pp. 171\u2013186 (Kluwer Academic Press)."},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00343-5"},{"key":"e_1_2_1_44_2","unstructured":"C. A.Rogers Hausdorff Measures (Cambridge University Press Cambridge 1998)."},{"key":"e_1_2_1_45_2","first-page":"219","article-title":"Coding of combinatorial sources and Hausdorff dimension","volume":"30","author":"Ryabko B. Ya.","year":"1984","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_46_2","first-page":"170","article-title":"Noiseless coding of combinatorial sources","volume":"22","author":"Ryabko B. Ya.","year":"1986","journal-title":"Problems of Information Transmission"},{"key":"e_1_2_1_47_2","first-page":"186","article-title":"Algorithmic approach to the prediction problem","volume":"29","author":"Ryabko B. Ya.","year":"1993","journal-title":"Problems of Information Transmission"},{"key":"e_1_2_1_48_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1994.1015"},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01694181"},{"key":"e_1_2_1_50_2","doi-asserted-by":"crossref","unstructured":"C. P.Schnorr Zuf\u00e4lligkeit und Wahrscheinlichkeit (Springer\u2010Verlag Berlin et al. 1971).","DOI":"10.1007\/BFb0112458"},{"key":"e_1_2_1_51_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(73)80030-3"},{"key":"e_1_2_1_52_2","doi-asserted-by":"crossref","unstructured":"C. P.Schnorr A survey of the theory of random sequences. In: Basic Problems in Methodology and Linguistics (R. E. Butts and J. Hintikka eds.) pp. 193\u2013210 (D. Reidel Dordrecht 1977).","DOI":"10.1007\/978-94-017-0837-1_12"},{"key":"e_1_2_1_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/j.1538-7305.1949.tb03624.x"},{"key":"e_1_2_1_54_2","first-page":"14","article-title":"The frequency approach to the definition of a random sequence","volume":"18","author":"Shen' A. Kh.","year":"1982","journal-title":"Semiotika i Informatika"},{"key":"e_1_2_1_55_2","first-page":"316","article-title":"On relations between different algorithmic definitions of randomness","volume":"38","author":"Shen' A. Kh.","year":"1989","journal-title":"Soviet Mathematics Doklady"},{"key":"e_1_2_1_56_2","unstructured":"R. M.Solovay1975. Reported in [9]."},{"key":"e_1_2_1_57_2","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1993.1017"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000086"},{"key":"e_1_2_1_59_2","doi-asserted-by":"crossref","unstructured":"L.Staiger How much can you win when your adversary is handicapped. In: Numbers Information and Complexity pp. 403\u2013412 (Kluwer Academic Press 2000).","DOI":"10.1007\/978-1-4757-6048-4_34"},{"key":"e_1_2_1_60_2","unstructured":"L.Staiger Constructive dimension equals Kolmogorov complexity. Technical Report CDMTCS\u2010210 University of Auckland January 2003."},{"key":"e_1_2_1_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392379"},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.14492\/hokmj\/1350911778"},{"key":"e_1_2_1_63_2","unstructured":"S. A.Terwijn Complexity and randomness. Technical Report CDMTCS\u2010212 University of Auckland March 2003."},{"key":"e_1_2_1_64_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100059119"},{"key":"e_1_2_1_65_2","unstructured":"J.Ville \u00c9tude Critique de la Notion de Collectif (Gauthier\u2010Villars Paris 1939)."},{"key":"e_1_2_1_66_2","doi-asserted-by":"publisher","DOI":"10.1070\/RM1970v025n06ABEH001269"}],"container-title":["Mathematical Logic Quarterly"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fmalq.200310127","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/malq.200310127","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,20]],"date-time":"2024-12-20T16:29:55Z","timestamp":1734712195000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/malq.200310127"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,11,25]]},"references-count":66,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1002\/malq.200310127"],"URL":"https:\/\/doi.org\/10.1002\/malq.200310127","archive":["Portico"],"relation":{},"ISSN":["0942-5616","1521-3870"],"issn-type":[{"type":"print","value":"0942-5616"},{"type":"electronic","value":"1521-3870"}],"subject":[],"published":{"date-parts":[[2004,11,25]]}}}