{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T15:23:32Z","timestamp":1773242612185,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540677154","type":"print"},{"value":"9783540450221","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-45022-x_76","type":"book-chapter","created":{"date-parts":[[2007,11,13]],"date-time":"2007-11-13T18:57:25Z","timestamp":1194980245000},"page":"902-913","source":"Crossref","is-referenced-by-count":29,"title":["Gales and the Constructive Dimension of Individual Sequences"],"prefix":"10.1007","author":[{"given":"Jack H.","family":"Lutz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2002,2,18]]},"reference":[{"key":"76_CR1","doi-asserted-by":"publisher","first-page":"605","DOI":"10.1016\/S0022-0000(05)80073-X","volume":"49","author":"J. Cai","year":"1994","unstructured":"J. Cai and J. Hartmanis. On Hausdorff and topological dimensions of the Kolmogorov complexity of the real line. Journal of Computer and Systems Sciences, 49:605\u2013619, 1994.","journal-title":"Journal of Computer and Systems Sciences"},{"key":"76_CR2","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G. J. Chaitin","year":"1966","unstructured":"G. J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association for Computing Machinery, 13:547\u2013569, 1966.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"76_CR3","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1145\/321495.321506","volume":"16","author":"G. J. Chaitin","year":"1969","unstructured":"G. J. Chaitin. On the length of programs for computing finite binary sequences: statistical considerations. Journal of the ACM, 16:145\u2013159, 1969.","journal-title":"Journal of the ACM"},{"key":"76_CR4","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G. J. Chaitin","year":"1975","unstructured":"G. J. Chaitin. A theory of program size formally identical to information theory. Journal of the Association for Computing Machinery, 22:329\u2013340, 1975.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"76_CR5","doi-asserted-by":"crossref","unstructured":"K. Falconer. The Geometry of Fractal Sets. Cambridge University Press, 1985.","DOI":"10.1017\/CBO9780511623738"},{"key":"76_CR6","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F. Hausdorff","year":"1919","unstructured":"F. Hausdorff. Dimension und \u00e4usseres Mass. Math. Ann., 79:157\u2013179, 1919.","journal-title":"Math. Ann."},{"key":"76_CR7","first-page":"369","volume":"25","author":"A. N. Kolmogorov","year":"1963","unstructured":"A. N. Kolmogorov. On tables of random numbers. Sankhy\u0101, Series A, 25:369\u2013376, 1963.","journal-title":"Sankhy\u0101, Series A"},{"key":"76_CR8","first-page":"1","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov. Three approaches to the quantitative definition of \u2018information\u2019. Problems of Information Transmission, 1:1\u20137, 1965.","journal-title":"Problems of Information Transmission"},{"key":"76_CR9","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1070\/RM1983v038n04ABEH004203","volume":"38","author":"A. N. Kolmogorov","year":"1983","unstructured":"A. N. Kolmogorov. Combinatorial foundations of information theory and calculus of probabilities. Russian Mathematical Surveys, 38:29\u201340, 1983.","journal-title":"Russian Mathematical Surveys"},{"key":"76_CR10","doi-asserted-by":"crossref","first-page":"265","DOI":"10.4064\/fm-37-1-265-285","volume":"37","author":"G. Kreisel","year":"1950","unstructured":"G. Kreisel. Note on arithmetical models for consistent formulae of the predicate calculus. Fundamenta Mathematicae, 37:265\u2013285, 1950.","journal-title":"Fundamenta Mathematicae"},{"key":"76_CR11","first-page":"1413","volume":"14","author":"L. A. Levin","year":"1973","unstructured":"L. A. Levin. On the notion of a random sequence. Soviet Mathematics Doklady, 14:1413\u20131416, 1973.","journal-title":"Soviet Mathematics Doklady"},{"key":"76_CR12","doi-asserted-by":"crossref","unstructured":"M. Li and P. M. B. Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, 1997.","DOI":"10.1007\/978-1-4757-2606-0"},{"key":"76_CR13","doi-asserted-by":"publisher","first-page":"497","DOI":"10.2307\/1994579","volume":"125","author":"D. W. Loveland","year":"1966","unstructured":"D. W. Loveland. The Kleene hierarchy classification of recursively random sequences. Transactions of the American Mathematical Society, 125:497\u2013510, 1966.","journal-title":"Transactions of the American Mathematical Society"},{"key":"76_CR14","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1002\/malq.19660120124","volume":"12","author":"D. W. Loveland","year":"1966","unstructured":"D. W. Loveland. A new interpretation of von Mises\u2019 concept of a random sequence. Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik, 12:279\u2013294, 1966.","journal-title":"Zeitschrift f\u00fcr Mathematische Logik und Grundlagen der Mathematik"},{"key":"76_CR15","doi-asserted-by":"crossref","unstructured":"J. H. Lutz. Dimension in complexity classes. In Proceedings of the Fifteenth Annual IEEE Conference on Computational Complexity. IEEE Computer Society Press, 2000.","DOI":"10.1109\/CCC.2000.856747"},{"key":"76_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":"P. Martin-L\u00f6f. The definition of random sequences. Information and Control, 9:602\u2013619, 1966.","journal-title":"Information and Control"},{"key":"76_CR17","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/BF00534110","volume":"19","author":"P. Martin-L\u00f6f","year":"1971","unstructured":"P. Martin-L\u00f6f. Complexity oscillations in infinite binary sequences. Zeitschrift f\u00fcr Wahrscheinlichkeitstheory und Verwandte Gebiete, 19:225\u2013230, 1971.","journal-title":"Zeitschrift f\u00fcr Wahrscheinlichkeitstheory und Verwandte Gebiete"},{"key":"76_CR18","unstructured":"P. Odifreddi. Classical Recursion Theory. Elsevier, 1989."},{"key":"76_CR19","first-page":"170","volume":"22","author":"B. Ya. Ryabko","year":"1986","unstructured":"B. Ya. Ryabko. Noiseless coding of combinatorial sources. Problems of Information Transmission, 22:170\u2013179, 1986.","journal-title":"Problems of Information Transmission"},{"key":"76_CR20","first-page":"186","volume":"29","author":"B. Ya. Ryabko","year":"1993","unstructured":"B. Ya. Ryabko. Algorithmic approach to the prediction problem. Problems of Information Transmission, 29:186\u2013193, 1993.","journal-title":"Problems of Information Transmission"},{"key":"76_CR21","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1006\/jcom.1994.1015","volume":"10","author":"B. Ya. Ryabko","year":"1994","unstructured":"B. Ya. Ryabko. The complexity and effectiveness of prediction problems. Journal of Complexity, 10:281\u2013295, 1994.","journal-title":"Journal of Complexity"},{"key":"76_CR22","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C. P. Schnorr","year":"1971","unstructured":"C. P. Schnorr. A unified approach to the definition of random sequences. Mathematical Systems Theory, 5:246\u2013258, 1971.","journal-title":"Mathematical Systems Theory"},{"key":"76_CR23","doi-asserted-by":"crossref","unstructured":"C. P. Schnorr. Zuf\u00e4lligkeit und Wahrscheinlichkeit. Lecture Notes in Mathematics, 218, 1971.","DOI":"10.1007\/BFb0112458"},{"key":"76_CR24","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C. P. Schnorr","year":"1973","unstructured":"C. P. Schnorr. Process complexity and effective random tests. Journal of Computer and System Sciences, 7:376\u2013388, 1973.","journal-title":"Journal of Computer and System Sciences"},{"key":"76_CR25","first-page":"14","volume":"18","author":"A. Kh. She\u0144","year":"1982","unstructured":"A. Kh. She\u0144. The frequency approach to the definition of a random sequence. Semiotika i Informatika, 18:14\u201342, 1982. (In Russian.).","journal-title":"Semiotika i Informatika"},{"key":"76_CR26","first-page":"316","volume":"38","author":"A. Kh. She\u0144","year":"1989","unstructured":"A. Kh. She\u0144. On relations between different algorithmic definitions of randomness. Soviet Mathematics Doklady, 38:316\u2013319, 1989.","journal-title":"Soviet Mathematics Doklady"},{"key":"76_CR27","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R. J. Solomonoff","year":"1964","unstructured":"R. J. Solomonoff. A formal theory of inductive inference. Information and Control, 7:1\u201322, 224\u2013254, 1964.","journal-title":"Information and Control"},{"key":"76_CR28","unstructured":"R. M. Solovay, 1975. reported in [?]."},{"key":"76_CR29","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1006\/inco.1993.1017","volume":"102","author":"L. Staiger","year":"1993","unstructured":"L. Staiger. Kolmogorov complexity and Hausdorff dimension. Information and Computation, 102:159\u2013194, 1993.","journal-title":"Information and Computation"},{"key":"76_CR30","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s002240000086","volume":"31","author":"L. Staiger","year":"1998","unstructured":"L. Staiger. A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Theory of Computing Systems, 31:215\u2013229, 1998.","journal-title":"Theory of Computing Systems"},{"key":"76_CR31","unstructured":"S. A. Terwijn. Personal communication, 2000."},{"key":"76_CR32","unstructured":"M. van Lambalgen. Random Sequences. PhD thesis, Department of Mathematics, University of Amsterdam, 1987."},{"key":"76_CR33","first-page":"656","volume":"35","author":"V. G. Vovk","year":"1987","unstructured":"V. G. Vovk. On a randomness criterion. Soviet Mathematics Doklady, 35:656\u2013660, 1987.","journal-title":"Soviet Mathematics Doklady"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45022-X_76","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,25]],"date-time":"2019-02-25T04:29:40Z","timestamp":1551068980000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45022-X_76"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540677154","9783540450221"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-45022-x_76","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2000]]}}}