{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T11:25:52Z","timestamp":1751887552488,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540609223"},{"type":"electronic","value":"9783540497233"}],"license":[{"start":{"date-parts":[[1996,1,1]],"date-time":"1996-01-01T00:00:00Z","timestamp":820454400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1996]]},"DOI":"10.1007\/3-540-60922-9_3","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T21:04:24Z","timestamp":1330290264000},"page":"25-36","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["On the complexity of random strings"],"prefix":"10.1007","author":[{"given":"Martin","family":"Kummer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,7]]},"reference":[{"key":"3_CR1","doi-asserted-by":"publisher","first-page":"304","DOI":"10.1006\/inco.1995.1115","volume":"120","author":"R. Beigel","year":"1995","unstructured":"R. Beigel, M. Kummer, F. Stephan. Approximable sets. Information and Computation, 120:304\u2013314, 1995.","journal-title":"Information and Computation"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"H. Buhrman, E. Mayordomo. An excursion to the Kolmogorov random strings. In: Proceedings Structure in Complexity Theory, Tenth Annual Conference, pp. 197\u2013203, 1995.","DOI":"10.1109\/SCT.1995.514858"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"H. Buhrman, P. Orponen. Random strings make hard instances. In: Proceedings Structure in Complexity Theory, Ninth Annual Conference, pp. 217\u2013222, 1994.","DOI":"10.1109\/SCT.1994.315802"},{"key":"3_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-03049-3","volume-title":"Information and randomness","author":"C. Calude","year":"1994","unstructured":"C. Calude. Information and randomness. Springer-Verlag, Berlin, 1994."},{"key":"3_CR5","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/0096-3003(93)90037-F","volume":"59","author":"G. J. Chaitin","year":"1993","unstructured":"G. J. Chaitin. On the number of n-bit strings with maximum complexity. Applied Mathematics and Computation, 59:97\u2013100, 1993.","journal-title":"Applied Mathematics and Computation"},{"key":"3_CR6","first-page":"198","volume":"57","author":"G. J. Chaitin","year":"1995","unstructured":"G. J. Chaitin, A. Arslanov, C. Calude. Program-size complexity computes the halting problem. Bulletin of the EATCS, 57:198\u2013200, 1995.","journal-title":"Bulletin of the EATCS"},{"key":"3_CR7","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/3-540-59119-2_177","volume":"904","author":"R. Freivalds","year":"1995","unstructured":"R. Freivalds, S. Jain. Kolmogorov numberings and minimal identification. In: Proceedings EuroCOLT'95, Lecture Notes in Computer Science, 904:182\u2013195, 1995.","journal-title":"Lecture Notes in Computer Science"},{"key":"3_CR8","doi-asserted-by":"crossref","first-page":"446","DOI":"10.2307\/2273042","volume":"38","author":"C. G. Jockusch","year":"1973","unstructured":"C. G. Jockusch, R. I. Soare. Post's problem and his hypersimple set. In: Journal of Symbolic Logic, 38:446\u2013452, 1973.","journal-title":"Journal of Symbolic Logic"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/3-540-60246-1_123","volume":"969","author":"S. Kaufmann","year":"1995","unstructured":"S. Kaufmann, M. Kummer. On a quantitative notion of uniformity. In: Proceedings MFCS'95, Lecture Notes in Computer Science, 969:169\u2013178, 1995.","journal-title":"Lecture Notes in Computer Science"},{"key":"3_CR10","first-page":"1","volume":"1","author":"A. N. Kolmogorov","year":"1965","unstructured":"A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems Inform. Transmission, 1:1\u20137, 1965.","journal-title":"Problems Inform. Transmission"},{"key":"3_CR11","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1006\/inco.1995.1099","volume":"120","author":"M. Kummer","year":"1995","unstructured":"M. Kummer, F. Stephan. Recursion theoretic properties of frequency computation and bounded queries. Information and Computation, 120:59\u201377, 1995.","journal-title":"Information and Computation"},{"key":"3_CR12","first-page":"429","volume":"48","author":"A. H. Lachlan","year":"1975","unstructured":"A. H. Lachlan. wtt-complete sets are not necessarily tt-complete. Proc. Amer. Math. Soc., 48:429\u2013434, 1975.","journal-title":"Proc. Amer. Math. Soc."},{"key":"3_CR13","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-3860-5","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1993","unstructured":"M. Li, P. Vit\u00e1nyi. An Introduction to Kolmogorov Complexity and its Applications. Springer-Verlag, New York, 1993."},{"key":"3_CR14","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1016\/S0022-0000(74)80003-6","volume":"9","author":"N. Lynch","year":"1974","unstructured":"N. Lynch. Approximations to the halting problem. Journal of Computer and System Sciences, 9:143\u2013150, 1974.","journal-title":"Journal of Computer and System Sciences"},{"key":"3_CR15","volume-title":"Classical recursion theory","author":"P. Odifreddi","year":"1989","unstructured":"P. Odifreddi. Classical recursion theory. North-Holland, Amsterdam, 1989."},{"key":"3_CR16","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1090\/S0002-9904-1944-08111-1","volume":"50","author":"E. L. Post","year":"1944","unstructured":"E. L. Post. Recursively enumerable sets of positive integers and their decision problems. Bull. Amer. Math. Soc., 50:284\u2013316, 1944.","journal-title":"Bull. Amer. Math. Soc."},{"key":"3_CR17","unstructured":"G. F. Rose. An extended notion of computability. In Abstr. Intern. Congr. for Logic, Meth., and Phil. of Science, Stanford, CA, 1960."},{"key":"3_CR18","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/BF01762189","volume":"8","author":"C. P. Schnorr","year":"1974","unstructured":"C. P. Schnorr. Optimal enumerations and optimal G\u00f6del numberings. Mathematical Systems Theory, 8:182\u2013191, 1974.","journal-title":"Mathematical Systems Theory"},{"key":"3_CR19","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":"R. I. Soare. Recursively enumerable sets and degrees. Springer-Verlag, Berlin, 1987."},{"key":"3_CR20","unstructured":"P. Vit\u00e1nyi. E-mail to the author. September 15, 1995."}],"container-title":["Lecture Notes in Computer Science","STACS 96"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60922-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:41Z","timestamp":1742598641000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60922-9_3"}},"subtitle":["Extended abstract"],"short-title":[],"issued":{"date-parts":[[1996]]},"ISBN":["9783540609223","9783540497233"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/3-540-60922-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1996]]},"assertion":[{"value":"7 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}