{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T00:42:43Z","timestamp":1777596163187,"version":"3.51.4"},"reference-count":55,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[2007,7,6]],"date-time":"2007-07-06T00:00:00Z","timestamp":1183680000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2008,12]]},"DOI":"10.1007\/s00224-007-9024-7","type":"journal-article","created":{"date-parts":[[2007,7,5]],"date-time":"2007-07-05T17:38:15Z","timestamp":1183657095000},"page":"425-463","source":"Crossref","is-referenced-by-count":8,"title":["Dimension Extractors and Optimal Decompression"],"prefix":"10.1007","volume":"43","author":[{"given":"David","family":"Doty","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,7,6]]},"reference":[{"key":"9024_CR1","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K.: Randomness, relativizations, and polynomial reducibilities. In: Proceedings of the First Structure in Complexity Theory Conference, pp.\u00a023\u201334 (1986)","DOI":"10.1007\/3-540-16486-3_87"},{"key":"9024_CR2","doi-asserted-by":"crossref","unstructured":"Athreya, K.B., Hitchcock, J.M., Lutz, J.H., Mayordomo, E.: Effective strong dimension, algorithmic information, and computational complexity. SIAM J.\u00a0Comput. (to\u00a0appear). Preliminary version appeared in Diekert,\u00a0V., Habib,\u00a0M. (eds.) Proceedings of the 21st International Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25\u201327, 2004. Lecture Notes in Computer Science, pp.\u00a0632\u2013643","DOI":"10.1007\/978-3-540-24749-4_55"},{"key":"9024_CR3","first-page":"1251","volume":"9","author":"Y.M. Barzdin\u2019","year":"1968","unstructured":"Barzdin\u2019, Y.M.: Complexity of programs to determine whether natural numbers not greater than n belong to a recursively enumerable set. Sov. Math. Dokl. 9, 1251\u20131254 (1968)","journal-title":"Sov. Math. Dokl."},{"key":"9024_CR4","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"C.H. Bennett","year":"1988","unstructured":"Bennett, C.H.: Logical depth and physical complexity. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp.\u00a0227\u2013257. Oxford University Press, London (1988)"},{"key":"9024_CR5","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.H. Bennett","year":"1981","unstructured":"Bennett, C.H., Gill, J.: Relative to a random oracle A, $\\mathsf{P}^{A}\\neq\\mathsf{NP}^{A}\\neq\\mathsf{co}\\mbox{-}\\mathsf{NP}^{A}$ with probability\u00a01. SIAM J.\u00a0Comput. 10, 96\u2013113 (1981)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9024_CR6","unstructured":"Bienvenu, L.: Personal communication (2006)"},{"key":"9024_CR7","doi-asserted-by":"crossref","unstructured":"Bienvenu, L., Doty, D., Stephan, F.: Constructive dimension and weak truth-table degrees. In: Cooper,\u00a0S.B., L\u00f6we,\u00a0B., Sorbi,\u00a0A. (eds.) Computation and Logic in the Real World\u2014Third Conference of Computability in Europe. Lecture Notes in Computer Science, vol.\u00a04497. Springer (2007)","DOI":"10.1007\/978-3-540-73001-9_7"},{"key":"9024_CR8","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF01578842","volume":"27","author":"R.V. Book","year":"1994","unstructured":"Book, R.V., Lutz, J.H., Wagner, K.W.: An observation on probability versus randomness with applications to complexity classes. Math. Syst. Theory 27, 201\u2013209 (1994)","journal-title":"Math. Syst. Theory"},{"key":"9024_CR9","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.tcs.2005.09.040","volume":"349","author":"C. Bourke","year":"2005","unstructured":"Bourke, C., Hitchcock, J.M., Vinodchandran, N.V.: Entropy rates and finite-state dimension. Theor. Comput. Sci. 349, 392\u2013406 (2005)","journal-title":"Theor. Comput. Sci."},{"key":"9024_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1007\/978-3-540-31856-9_34","volume-title":"Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science","author":"H. Buhrman","year":"2005","unstructured":"Buhrman, H., Fortnow, L., Newman, I., Vereshchagin, N.: Increasing Kolmogorov complexity. In: Proceedings of the 22nd Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol.\u00a03404, pp.\u00a0412\u2013421. Springer, Berlin (2005)"},{"key":"9024_CR11","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"G.J. Chaitin","year":"1975","unstructured":"Chaitin, G.J.: A theory of program size formally identical to information theory. J.\u00a0Assoc. Comput. Mach. 22, 329\u2013340 (1975)","journal-title":"J.\u00a0Assoc. Comput. Mach."},{"key":"9024_CR12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(03)00244-5","volume":"310","author":"J.J. Dai","year":"2004","unstructured":"Dai, J.J., Lathrop, J.I., Lutz, J.H., Mayordomo, E.: Finite-state dimension. Theor. Comput. Sci. 310, 1\u201333 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9024_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1007\/11780342_17","volume-title":"Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30\u2013July 5, 2006, Proceedings","author":"D. Doty","year":"2006","unstructured":"Doty, D.: Every sequence is decompressible from a random one. In: Beckmann, A., Berger, U., L\u00f6we, B., Tucker, J.V. (eds.) Logical Approaches to Computational Barriers, Second Conference on Computability in Europe, CiE 2006, Swansea, UK, June 30\u2013July 5, 2006, Proceedings. Lecture Notes in Computer Science, vol.\u00a03988, pp.\u00a0153\u2013162. Springer, New York (2006)"},{"key":"9024_CR14","doi-asserted-by":"crossref","unstructured":"Doty, D., Moser, P.: Finite-state dimension and lossy decompressors. Technical Report cs.CC\/0609096, Computing Research Repository (2006)","DOI":"10.1007\/11786986_47"},{"key":"9024_CR15","volume-title":"Classics on Fractals","author":"G.A. Edgar","year":"2004","unstructured":"Edgar, G.A.: Classics on Fractals. Westview Press, Oxford (2004)"},{"key":"9024_CR16","unstructured":"Fenner, S.A.: Gales and supergales are equivalent for defining constructive Hausdorff dimension. Technical Report cs.CC\/0208044, Computing Research Repository (2002)"},{"key":"9024_CR17","volume-title":"Proceedings of the 33rd International Colloquium on Automata, Languages and Programming","author":"L. Fortnow","year":"2006","unstructured":"Fortnow, L., Hitchcock, J., Pavan, A., Vinodchandran, N.V., Wang, F.: Extracting Kolmogorov complexity with applications to dimension zero-one laws. In: Proceedings of the 33rd International Colloquium on Automata, Languages and Programming. Springer, New York (2006)"},{"key":"9024_CR18","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1016\/S0019-9958(86)80004-3","volume":"70","author":"P. G\u00e1cs","year":"1986","unstructured":"G\u00e1cs, P.: Every sequence is reducible to a random one. Inf. Control 70, 186\u2013192 (1986)","journal-title":"Inf. Control"},{"key":"9024_CR19","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J.: Computational complexity of probabilistic Turing machines. SIAM J. Comput. 6, 675\u2013695 (1977)","journal-title":"SIAM J. Comput."},{"key":"9024_CR20","first-page":"471","volume-title":"Proceedings of the Thirtieth International Symposium on Mathematical Foundations of Computer Science","author":"X. Gu","year":"2006","unstructured":"Gu, X., Lutz, J.H.: Dimension characterizations of complexity classes. In: Proceedings of the Thirtieth International Symposium on Mathematical Foundations of Computer Science, pp.\u00a0471\u2013479. Springer, New York (2006)"},{"key":"9024_CR21","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF01457179","volume":"79","author":"F. Hausdorff","year":"1919","unstructured":"Hausdorff, F.: Dimension und \u00e4u\u00dferes Ma\u00df. Math. Ann. 79, 157\u2013179 (1919). English version appears in\u00a0[15], pp.\u00a075\u201399","journal-title":"Math. Ann."},{"key":"9024_CR22","unstructured":"Hitchcock, J.M.: Effective fractal dimension: foundations and applications. Ph.D.\u00a0Thesis, Iowa State University (2003)"},{"issue":"1\u20133","key":"9024_CR23","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/S0304-3975(03)00138-5","volume":"304","author":"J.M. Hitchcock","year":"2003","unstructured":"Hitchcock, J.M.: Fractal dimension and logarithmic loss unpredictability. Theor. Comput. Sci. 304(1\u20133), 431\u2013441 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9024_CR24","doi-asserted-by":"crossref","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. Inf. Process. Lett. 86(1), 9\u201312 (2003)","journal-title":"Inf. Process. Lett."},{"key":"9024_CR25","unstructured":"Hitchcock, J.M.: Personal communication (2006)"},{"key":"9024_CR26","unstructured":"Huffman, D.A.: Canonical forms for information-lossless finite-state logical machines. In: IRE Trans. Circuit Theory CT-6 (Special Supplement), pp.\u00a041\u201359 (1959). Also available in Moore,\u00a0E.F. (ed.) Sequential Machine: Selected Papers, pp.\u00a0866\u2013871. Addison-Wesley (1964)"},{"key":"9024_CR27","volume-title":"Switching and Finite Automata Theory","author":"Z. Kohavi","year":"1978","unstructured":"Kohavi, Z.: Switching and Finite Automata Theory, 2nd\u00a0edn. McGraw-Hill, New York (1978)","edition":"2"},{"key":"9024_CR28","doi-asserted-by":"crossref","unstructured":"Ku\u010dera, A.: Measure, \u03a0 1 0 -classes and complete extensions of PA. In: Recursion Theory Week. Lecture Notes in Mathematics, vol.\u00a01141, pp.\u00a0245\u2013259 (1985)","DOI":"10.1007\/BFb0076224"},{"key":"9024_CR29","doi-asserted-by":"crossref","unstructured":"Ku\u010dera, A.: On the use of diagonally nonrecursive functions. In: Studies in Logic and the Foundations of Mathematics, vol.\u00a0129, pp.\u00a0219\u2013239. North-Holland (1989)","DOI":"10.1016\/S0049-237X(08)70130-7"},{"key":"9024_CR30","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\u00a0edn. Springer, Berlin (1997)","edition":"2"},{"issue":"2","key":"9024_CR31","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/0022-0000(92)90020-J","volume":"44","author":"J.H. Lutz","year":"1992","unstructured":"Lutz, J.H.: Almost everywhere high nonuniform complexity. J.\u00a0Comput. Syst. Sci. 44(2), 220\u2013258 (1992)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"issue":"5","key":"9024_CR32","doi-asserted-by":"crossref","first-page":"1075","DOI":"10.1137\/0222065","volume":"22","author":"J.H. Lutz","year":"1993","unstructured":"Lutz, J.H.: A pseudorandom oracle characterization of BPP. SIAM J.\u00a0Comput. 22(5), 1075\u20131086 (1993)","journal-title":"SIAM J.\u00a0Comput."},{"key":"9024_CR33","doi-asserted-by":"crossref","first-page":"1236","DOI":"10.1137\/S0097539701417723","volume":"32","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: Dimension in complexity classes. SIAM J. Comput. 32, 1236\u20131259 (2003)","journal-title":"SIAM J. Comput."},{"key":"9024_CR34","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1016\/S0890-5401(03)00187-1","volume":"187","author":"J.H. Lutz","year":"2003","unstructured":"Lutz, J.H.: The dimensions of individual strings and sequences. Inf. Comput. 187, 49\u201379 (2003)","journal-title":"Inf. Comput."},{"key":"9024_CR35","doi-asserted-by":"crossref","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. Inf. Control 9, 602\u2013619 (1966)","journal-title":"Inf. Control"},{"issue":"1","key":"9024_CR36","doi-asserted-by":"crossref","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. Inf. Process. Lett. 84(1), 1\u20133 (2002)","journal-title":"Inf. Process. Lett."},{"key":"9024_CR37","doi-asserted-by":"crossref","unstructured":"Merkle, W., Mihailovi\u0107, N.: On the construction of effective random sets. J.\u00a0Symb. Log. 862\u2013878 (2004)","DOI":"10.2178\/jsl\/1096901772"},{"key":"9024_CR38","unstructured":"Miller, J.S., Nies, A.: Randomness and computability: open questions. Technical Report, University of Auckland (2005)"},{"key":"9024_CR39","unstructured":"Nies, A., Reimann, J.: A lower cone in the wtt degrees of non-integral effective dimension. In: Proceedings of IMS Workshop on Computational Prospects of Infinity (2006, to appear)"},{"key":"9024_CR40","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"9024_CR41","unstructured":"Reimann, J.: Computability and fractal dimension. Ph.D.\u00a0Thesis, Universit\u00e4t Heidelberg (2004)"},{"key":"9024_CR42","first-page":"219","volume":"30","author":"B.Y. Ryabko","year":"1984","unstructured":"Ryabko, B.Y.: Coding of combinatorial sources and Hausdorff dimension. Sov. Math. Dokl. 30, 219\u2013222 (1984)","journal-title":"Sov. Math. Dokl."},{"key":"9024_CR43","first-page":"170","volume":"22","author":"B.Y. Ryabko","year":"1986","unstructured":"Ryabko, B.Y.: Noiseless coding of combinatorial sources. Prob. Inf. Transm. 22, 170\u2013179 (1986)","journal-title":"Prob. Inf. Transm."},{"key":"9024_CR44","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C.P. Schnorr","year":"1971","unstructured":"Schnorr, C.P.: A unified approach to the definition of random sequences. Math. Syst. Theory 5, 246\u2013258 (1971)","journal-title":"Math. Syst. Theory"},{"key":"9024_CR45","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"C.P. Schnorr","year":"1973","unstructured":"Schnorr, C.P.: Process complexity and effective random tests. J.\u00a0Comput. Syst. Sci. 7, 376\u2013388 (1973)","journal-title":"J.\u00a0Comput. Syst. Sci."},{"key":"9024_CR46","first-page":"67","volume":"77","author":"R. Shaltiel","year":"2002","unstructured":"Shaltiel, R.: Recent developments in explicit constructions of extractors. Bull. EATCS 77, 67\u201395 (2002)","journal-title":"Bull. EATCS"},{"key":"9024_CR47","doi-asserted-by":"crossref","unstructured":"Shannon, C.E.: A mathematical theory of communication. Bell Syst. Tech.\u00a0J. 27, 379\u2013423, 623\u2013656 (1948)","DOI":"10.1002\/j.1538-7305.1948.tb01338.x"},{"key":"9024_CR48","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-02460-7","volume-title":"Recursively Enumerable Sets and Degrees","author":"R.I. Soare","year":"1987","unstructured":"Soare, R.I.: Recursively Enumerable Sets and Degrees. Springer, Berlin (1987)"},{"key":"9024_CR49","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1007\/BF02392379","volume":"153","author":"D. Sullivan","year":"1984","unstructured":"Sullivan, D.: Entropy, Hausdorff measures old and new, and limit sets of geometrically finite Kleinian groups. Acta Math. 153, 259\u2013277 (1984)","journal-title":"Acta Math."},{"key":"9024_CR50","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1017\/S0305004100059119","volume":"91","author":"C. Tricot","year":"1982","unstructured":"Tricot, C.: Two definitions of fractional dimension. Math. Proc. Camb. Philos. Soc. 91, 57\u201374 (1982)","journal-title":"Math. Proc. Camb. Philos. Soc."},{"key":"9024_CR51","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"676","DOI":"10.1007\/11549345_58","volume-title":"MFCS","author":"M.L. Vald\u00e9s","year":"2005","unstructured":"Vald\u00e9s, M.L., Mayordomo, E.: Dimension is compression. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS. Lecture Notes in Computer Science, vol.\u00a03618, pp.\u00a0676\u2013685. Springer, New York (2005)"},{"issue":"1\u20132","key":"9024_CR52","doi-asserted-by":"crossref","first-page":"131","DOI":"10.1016\/S0304-3975(01)00036-6","volume":"271","author":"N.K. Vereshchagin","year":"2002","unstructured":"Vereshchagin, N.K., Vyugin, M.V.: Independent minimum length programs to translate between given strings. Theor. Comput. Sci. 271(1\u20132), 131\u2013143 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"9024_CR53","first-page":"768","volume-title":"von\u00a0Neumann\u2019s Collected Works","author":"J. Neumann von","year":"1963","unstructured":"von Neumann, J.: Various techniques for use in connection with random digits. In: von\u00a0Neumann\u2019s Collected Works, vol.\u00a05, pp.\u00a0768\u2013770. Pergamon, Oxford (1963)"},{"key":"9024_CR54","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J. Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24, 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9024_CR55","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"A.K. Zvonkin","year":"1970","unstructured":"Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25, 83\u2013124 (1970)","journal-title":"Russ. Math. Surv."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9024-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9024-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9024-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T11:51:34Z","timestamp":1558698694000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9024-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,7,6]]},"references-count":55,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2008,12]]}},"alternative-id":["9024"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9024-7","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,7,6]]}}}