{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,18]],"date-time":"2026-03-18T02:25:10Z","timestamp":1773800710969,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642038150","type":"print"},{"value":"9783642038167","type":"electronic"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03816-7_34","type":"book-chapter","created":{"date-parts":[[2009,8,19]],"date-time":"2009-08-19T14:43:03Z","timestamp":1250692983000},"page":"392-402","source":"Crossref","is-referenced-by-count":5,"title":["Time-Bounded Kolmogorov Complexity and Solovay Functions"],"prefix":"10.1007","author":[{"given":"Rupert","family":"H\u00f6lzl","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thorsten","family":"Kr\u00e4ling","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wolfgang","family":"Merkle","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"34_CR1","unstructured":"Barmpalias, G., Downey, R., Greenberg, N.: K-trivial degrees and the jump-traceability hierarchy. Proc. Amer. Math. Soc.; posted on January 22, 2009, PII S 0002-9939(09)09761-5 (to appear in print)"},{"key":"34_CR2","first-page":"1251","volume":"9","author":"J.M. Barzdins","year":"1968","unstructured":"Barzdins, J.M.: Complexity of programs to determine whether natural numbers not greater than n belong to a computably enumerable set. Soviet Math.\u00a0Dokl.\u00a09, 1251\u20131254 (1968)","journal-title":"Soviet Math.\u00a0Dokl."},{"key":"34_CR3","unstructured":"Bienvenu, L., Downey, R.: Kolmogorov Complexity and Solovay Functions. In: Symposium on Theoretical Aspects of Computer Science , STACS 2009, pp. 147\u2013158 (2009), http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1810"},{"key":"34_CR4","doi-asserted-by":"crossref","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness (manuscript, 2009)","DOI":"10.1007\/978-0-387-68441-3"},{"issue":"2","key":"34_CR5","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/0304-3975(94)00014-X","volume":"132","author":"D. Juedes","year":"1994","unstructured":"Juedes, D., Lathrop, J., Lutz, J.: Computational depth and reducibility. Theor. Comput. Sci.\u00a0132(2), 37\u201370 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"1123","DOI":"10.1137\/S0097539794268789","volume":"25","author":"M. Kummer","year":"1996","unstructured":"Kummer, M.: Kolmogorov complexity and instance complexity of recursively enumerable sets. SIAM Journal on Computing\u00a025, 1123\u20131143 (1996)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR7","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1137\/S0097539799357441","volume":"31","author":"A. Ku\u010dera","year":"2001","unstructured":"Ku\u010dera, A., Slaman, T.: Randomness and recursive enumerability. SIAM Journal on Computing\u00a031, 199\u2013211 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"34_CR8","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-49820-1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"M. Li","year":"2008","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Heidelberg (2008)","edition":"3"},{"key":"34_CR9","doi-asserted-by":"crossref","unstructured":"Miller, J.S.: The K-degrees, low for K-degrees and weakly low for K-degrees. Notre Dame Journal of Formal Logic (to appear)","DOI":"10.1215\/00294527-2009-017"},{"key":"34_CR10","volume-title":"Computability and Randomness","author":"A. Nies","year":"2008","unstructured":"Nies, A.: Computability and Randomness. Oxford University Press, Oxford (2008)"},{"key":"34_CR11","unstructured":"Solovay, R.: Draft of a paper (or series of papers) on Chaitin\u2019s work. Unpublished notes, 215 pages (1975)"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2009"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03816-7_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,22]],"date-time":"2019-05-22T02:33:45Z","timestamp":1558492425000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03816-7_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642038150","9783642038167"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03816-7_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009]]}}}