{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,23]],"date-time":"2025-02-23T05:10:56Z","timestamp":1740287456915,"version":"3.37.3"},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540408017"},{"type":"electronic","value":"9783540452201"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-45220-1_21","type":"book-chapter","created":{"date-parts":[[2010,6,25]],"date-time":"2010-06-25T23:33:58Z","timestamp":1277508838000},"page":"241-254","source":"Crossref","is-referenced-by-count":2,"title":["The Arithmetical Complexity of Dimension and Randomness"],"prefix":"10.1007","author":[{"given":"John M.","family":"Hitchcock","sequence":"first","affiliation":[]},{"given":"Jack H.","family":"Lutz","sequence":"additional","affiliation":[]},{"given":"Sebastiaan A.","family":"Terwijn","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K., Merkle, W., Reimann, J., Stephan, F.: Hausdorff dimension in exponential time. In: Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 210\u2013217 (2001)","DOI":"10.1109\/CCC.2001.933888"},{"key":"21_CR2","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension, algorithmic information, and computational complexity. Technical Report cs.CC\/0211025, Computing Research Repository (2002)"},{"key":"21_CR3","unstructured":"Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theoretical Computer Science (to appear)"},{"key":"21_CR4","unstructured":"Fenner, S.A.: Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report cs.CC\/0208044, Computing Research Repository (2002)"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Lutz, J.H.: Prediction and dimension. In: Proceedings of the 15th Annual Conference on Computational Learning Theory, pp. 380\u2013395 (2002)","DOI":"10.1007\/3-540-45435-7_26"},{"key":"21_CR6","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F. Hausdorff","year":"1919","unstructured":"Hausdorff, F.: Dimension und \u00e4usseres Mass. Mathematische Annalen\u00a079, 157\u2013179 (1919)","journal-title":"Mathematische Annalen"},{"key":"21_CR7","doi-asserted-by":"crossref","unstructured":"Hitchcock, J.M.: Fractal dimension and logarithmic loss unpredictability. Theoretical Computer Science (to appear)","DOI":"10.1016\/S0304-3975(03)00138-5"},{"issue":"1","key":"21_CR8","doi-asserted-by":"publisher","first-page":"861","DOI":"10.1016\/S0304-3975(01)00340-1","volume":"289","author":"J.M. Hitchcock","year":"2002","unstructured":"Hitchcock, J.M.: MAX3SAT is exponentially hard to approximate if NP has positive dimension. Theoretical Computer Science\u00a0289(1), 861\u2013869 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"21_CR9","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/S0020-0190(02)00454-4","volume":"86","author":"J.M. Hitchcock","year":"2003","unstructured":"Hitchcock, J.M.: Gales suffice for constructive dimension. Information Processing Letters\u00a086(1), 9\u201312 (2003)","journal-title":"Information Processing Letters"},{"key":"21_CR10","series-title":"London Mathematical Society Lecture Notes Series","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1017\/CBO9780511629181.004","volume-title":"Recursion Theory: its Generalizations and Applications","author":"C.G. Jockusch","year":"1980","unstructured":"Jockusch, C.G.: Degrees of generic sets. In: Recursion Theory: its Generalizations and Applications. London Mathematical Society Lecture Notes Series, vol.\u00a045, pp. 110\u2013139. Cambridge University Press, Cambridge (1980)"},{"key":"21_CR11","doi-asserted-by":"crossref","first-page":"163","DOI":"10.4064\/fm-144-2-163-179","volume":"144","author":"H. Ki","year":"1994","unstructured":"Ki, H., Linton, T.: Normal numbers and subsets of \u2115 with given densities. Fundamenta Mathematicae\u00a0144, 163\u2013179 (1994)","journal-title":"Fundamenta Mathematicae"},{"key":"21_CR12","doi-asserted-by":"crossref","first-page":"265","DOI":"10.4064\/fm-37-1-265-285","volume":"37","author":"G. Kreisel","year":"1950","unstructured":"Kreisel, G.: Note on arithmetical models for consistent formulae of the predicate calculus. Fundamenta Mathematicae\u00a037, 265\u2013285 (1950)","journal-title":"Fundamenta Mathematicae"},{"key":"21_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997)","edition":"2"},{"key":"21_CR14","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM Journal on Computing (to appear)"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Lutz, J.H.: The dimensions of individual strings and sequences. Information and Computation (to appear)","DOI":"10.1016\/S0890-5401(03)00187-1"},{"key":"21_CR16","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information and Control\u00a09, 602\u2013619 (1966)","journal-title":"Information and Control"},{"issue":"1","key":"21_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0020-0190(02)00343-5","volume":"84","author":"E. Mayordomo","year":"2002","unstructured":"Mayordomo, E.: A Kolmogorov complexity characterization of constructive Hausdorff dimension. Information Processing Letters\u00a084(1), 1\u20133 (2002)","journal-title":"Information Processing Letters"},{"key":"21_CR18","series-title":"Studies in Logic and the Foundations of Mathematics","volume-title":"Classical recursion theory","author":"P. Odifreddi","year":"1989","unstructured":"Odifreddi, P.: Classical recursion theory. Studies in Logic and the Foundations of Mathematics, vol.\u00a0125. North-Holland, Amsterdam (1989)"},{"key":"21_CR19","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967)"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Schnorr, C.P.: Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, vol. 218 (1971)","DOI":"10.1007\/BFb0112458"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Staiger, L.: Recursive automata on infinite words. In: Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science, pp. 629\u2013639 (1993)","DOI":"10.1007\/3-540-56503-5_62"},{"key":"21_CR22","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1007\/978-1-4471-0751-4_22","volume-title":"Finite Versus Infinite: Contributions to an Eternal Dilemma","author":"L. Staiger","year":"2000","unstructured":"Staiger, L.: On the power of reading the whole infinite input tape. In: Calude, C.S., Paun, G. (eds.) Finite Versus Infinite: Contributions to an Eternal Dilemma, pp. 335\u2013348. Springer, Heidelberg (2000)"},{"key":"21_CR23","unstructured":"Staiger, L.: Constructive dimension equals Kolmogorov complexity. Technical Report CDMTCS-210, University of Auckland (January 2003)"},{"key":"21_CR24","unstructured":"Terwijn, S.A.: Complexity and randomness. Technical Report CDMTCS-212, University of Auckland, Notes for a course given at the University of Auckland (March 2003)"},{"key":"21_CR25","unstructured":"van Lambalgen, M.: Random Sequences. PhD thesis, Department of Mathematics, University of Amsterdam (1987)"},{"key":"21_CR26","unstructured":"Ville, J.: \u00c9tude Critique de la Notion de Collectif. Gauthier\u2013Villars, Paris (1939)"},{"key":"21_CR27","unstructured":"Wang, Y.: Randomness and Complexity. PhD thesis, Department of Mathematics, University of Heidelberg (1996)"}],"container-title":["Lecture Notes in Computer Science","Computer Science Logic"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-45220-1_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,22]],"date-time":"2025-02-22T08:00:08Z","timestamp":1740211208000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-45220-1_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540408017","9783540452201"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-45220-1_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}