{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:51:35Z","timestamp":1725562295734},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642152399"},{"type":"electronic","value":"9783642152405"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-15240-5_19","type":"book-chapter","created":{"date-parts":[[2010,8,4]],"date-time":"2010-08-04T15:30:15Z","timestamp":1280935815000},"page":"259-270","source":"Crossref","is-referenced-by-count":1,"title":["Initial Segment Complexities of Randomness Notions"],"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":"Frank","family":"Stephan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Guohua","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"19_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-540-73420-8_56","volume-title":"Automata, Languages and Programming","author":"L. Bienvenu","year":"2007","unstructured":"Bienvenu, L., Merkle, W.: Reconciling Data Compression and Kolmogorov Complexity. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 643\u2013654. Springer, Heidelberg (2007)"},{"key":"19_CR2","volume-title":"An Algorithmic Perspective","author":"C.S. Calude","year":"2002","unstructured":"Calude, C.S.: Information and Randomness. In: An Algorithmic Perspective, 2nd edn., Springer, Heidelberg (2002)","edition":"2"},{"key":"19_CR3","doi-asserted-by":"publisher","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. Journal of the ACM\u00a022, 329\u2013340 (1975)","journal-title":"Journal of the ACM"},{"key":"19_CR4","doi-asserted-by":"publisher","first-page":"1044","DOI":"10.2178\/jsl\/1154698590","volume":"71","author":"R. Downey","year":"2006","unstructured":"Downey, R., Nies, A., Weber, R., Yu, L.: Lowness and $\\Pi_2^0$ Nullsets. Journal of Symbolic Logic\u00a071, 1044\u20131052 (2006)","journal-title":"Journal of Symbolic Logic"},{"key":"19_CR5","doi-asserted-by":"publisher","first-page":"533","DOI":"10.2178\/jsl\/1082418542","volume":"69","author":"R. Downey","year":"2004","unstructured":"Downey, R., Griffiths, E.: On Schnorr randomness. Journal of Symbolic Logic\u00a069, 533\u2013554 (2004)","journal-title":"Journal of Symbolic Logic"},{"key":"19_CR6","doi-asserted-by":"publisher","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. Information and Control\u00a070, 186\u2013192 (1986)","journal-title":"Information and Control"},{"key":"19_CR7","series-title":"LNM","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1007\/BFb0076224","volume-title":"Recursion Theory Week","author":"A. Ku\u010dera","year":"1985","unstructured":"Ku\u010dera, A.: Measure, $\\Pi^0_1$ -classes and complete extensions of PA. In: PPSN 1996. LNM, vol.\u00a01141, pp. 245\u2013259. Springer, Heidelberg (1985)"},{"key":"19_CR8","unstructured":"Kurtz, S.A.: Randomness and genericity in the degrees of unsolvatibility. PhD dissertation, University of Illinois at Urbana-Champaign (1981)"},{"key":"19_CR9","doi-asserted-by":"crossref","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":"19_CR10","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"},{"key":"19_CR11","doi-asserted-by":"publisher","first-page":"907","DOI":"10.2178\/jsl\/1096901774","volume":"69","author":"J.S. Miller","year":"2004","unstructured":"Miller, J.S.: Every 2-random real is Kolmogorov random. Journal of Symbolic Logic\u00a069, 907\u2013913 (2004)","journal-title":"Journal of Symbolic Logic"},{"key":"19_CR12","unstructured":"Miller, J.S.: The K-degrees, low for K degrees and weakly low for K oracles. Notre Dame Journal of Formal Logic (to appear)"},{"key":"19_CR13","doi-asserted-by":"crossref","unstructured":"Nies, A.: Computability and Randomness. Oxford Science Publications (2009)","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"19_CR14","doi-asserted-by":"publisher","first-page":"515","DOI":"10.2178\/jsl\/1120224726","volume":"70","author":"A. Nies","year":"2005","unstructured":"Nies, A., Stephan, F., Terwijn, S.A.: Randomness, relativization and Turing degrees. Journal of Symbolic Logic\u00a070, 515\u2013535 (2005)","journal-title":"Journal of Symbolic Logic"},{"key":"19_CR15","volume-title":"Classical Recursion Theory I","author":"P. Odifreddi","year":"1989","unstructured":"Odifreddi, P.: Classical Recursion Theory I. North-Holland, Amsterdam (1989)"},{"key":"19_CR16","volume-title":"Classical Recursion Theory II","author":"P. Odifreddi","year":"1999","unstructured":"Odifreddi, P.: Classical Recursion Theory II. Elsevier, Amsterdam (1999)"},{"key":"19_CR17","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1017\/S1755020308080076","volume":"1","author":"D. Osherson","year":"2008","unstructured":"Osherson, D., Weinstein, S.: Recognizing the strong random reals. The Review of Symbolic Logic\u00a01, 56\u201363 (2008)","journal-title":"The Review of Symbolic Logic"},{"key":"19_CR18","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology","year":"1971","unstructured":"Williams, H.C. (ed.): CRYPTO 1985. LNCS, vol.\u00a0218. Springer, Heidelberg (1971)"},{"key":"19_CR19","doi-asserted-by":"publisher","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. Journal of Computer and System Sciences\u00a07, 376\u2013388 (1973)","journal-title":"Journal of Computer and System Sciences"},{"key":"19_CR20","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, Heidelberg (1987)"},{"key":"19_CR21","doi-asserted-by":"crossref","unstructured":"Stephan, F.: Martin-L\u00f6f Random and PA-complete Sets. In: Proceedings of ASL Logic Colloquium 2002. ASL Lecture Notes in Logic, vol.\u00a027, pp. 342\u2013348 (2006)","DOI":"10.1017\/9781316755723.016"},{"key":"19_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/11494645_57","volume-title":"New Computational Paradigms","author":"F. Stephan","year":"2005","unstructured":"Stephan, F., Wu, G.: Presentations of K-Trivial Reals and Kolmogorov Complexity. In: Cooper, S.B., L\u00f6we, B., Torenvliet, L. (eds.) CiE 2005. LNCS, vol.\u00a03526, pp. 461\u2013469. Springer, Heidelberg (2005)"}],"container-title":["IFIP Advances in Information and Communication Technology","Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-15240-5_19.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,24]],"date-time":"2020-11-24T03:03:19Z","timestamp":1606186999000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-15240-5_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642152399","9783642152405"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-15240-5_19","relation":{},"ISSN":["1868-4238","1861-2288"],"issn-type":[{"type":"print","value":"1868-4238"},{"type":"electronic","value":"1861-2288"}],"subject":[],"published":{"date-parts":[[2010]]}}}