{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T07:06:22Z","timestamp":1769065582326,"version":"3.49.0"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2015,1,27]],"date-time":"2015-01-27T00:00:00Z","timestamp":1422316800000},"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":["Theory Comput Syst"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00224-014-9604-2","type":"journal-article","created":{"date-parts":[[2015,1,26]],"date-time":"2015-01-26T01:47:34Z","timestamp":1422236854000},"page":"424-440","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["The Sum 2 KM(x)\u2212K(x) Over All Prefixes x of Some Binary Sequence Can be Infinite"],"prefix":"10.1007","volume":"58","author":[{"given":"Mikhail","family":"Andreev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akim","family":"Kumok","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,1,27]]},"reference":[{"key":"9604_CR1","doi-asserted-by":"crossref","unstructured":"Bienvenu, L., G\u00e1cs, P., Hoyrup, M., Rojas, C., Shen, A.: Algorithmic tests and randomness with respect to a class of measures In: Proceeding of the Steklov Institute of Mathematics, Vol. 274, pp 41\u2013102 (2011). arXiv: 1103.1529v2","DOI":"10.1134\/S0081543811060058"},{"key":"9604_CR2","unstructured":"Shen, A. Algoritmic information theory and Kolmogorov complexity, lecture notes, http:\/\/www.it.uu.se\/research\/publications\/reports\/2000-034"},{"key":"9604_CR3","volume-title":"Kolmogorov Complexity and Algorithmic Randomness","author":"NK Vereshchagin","year":"2013","unstructured":"Vereshchagin, N.K., Uspensky, V.A., Shen, A.: Kolmogorov Complexity and Algorithmic Randomness. MCCME Publishers, Moscow (2013). (In Russian)"},{"key":"9604_CR4","first-page":"53","volume-title":"Some Theorems About the Algorithmic Approach to Probability Theory and Information Theory","author":"L Levin","year":"1971","unstructured":"Levin, L.: Some Theorems About the Algorithmic Approach to Probability Theory and Information Theory, p 53. Ph.D. thesis, Moscow State University (1971). (In Russian)"},{"key":"9604_CR5","first-page":"206","volume":"10","author":"LA Levin","year":"1974","unstructured":"Levin, L.A.: Laws on information conservation (nongrowth) and aspects of the foundation of probability theory. Probl. Inf. Transm. 10, 206\u2013210 (1974)","journal-title":"Probl. Inf. Transm."},{"issue":"5","key":"9604_CR6","first-page":"1477","volume":"15","author":"P G\u00e1cs","year":"1974","unstructured":"G\u00e1cs, P.: On the symmetry of algorithmic information. Soviet Math. Dokl. 15(5), 1477\u20131480 (1974)","journal-title":"Soviet Math. Dokl."},{"issue":"3","key":"9604_CR7","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1145\/321892.321894","volume":"22","author":"GJ Chaitin","year":"1975","unstructured":"Chaitin, G.J.: A theory of program size formally identical to information theory. J. ACM 22(3), 329\u2013340 (1975)","journal-title":"J. ACM"},{"issue":"6(156","key":"9604_CR8","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1070\/RM1970v025n06ABEH001269","volume":"25","author":"AK Zvonkin","year":"1970","unstructured":"Zvonkin, A.K., Levin, L.A.: The complexity of finite objects and the developments of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25(6(156)), 83\u2013124 (1970)","journal-title":"Russ. Math. Surv."},{"key":"9604_CR9","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."},{"key":"9604_CR10","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1002\/malq.19800262502","volume":"26","author":"P G\u00e1cs","year":"1979","unstructured":"G\u00e1cs, P.: Exact expressions for some randomness tests. Zeitschrift f. Math. Logik und Grundlagen d. Math. 26, 385\u2013394 (1979)","journal-title":"Zeitschrift f. Math. Logik und Grundlagen d. Math."},{"key":"9604_CR11","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1016\/S0022-0000(73)80030-3","volume":"7","author":"CP Schnorr","year":"1973","unstructured":"Schnorr, C. P.: Process complexity and effective random tests. J. Comput. Syst. Sci. 7, 376\u2013388 (1973). Preliminary version: In: Proceedings of the 4th ACM Symposium on Theory of Computing (STOC), 1972, pp. 168\u2013176","journal-title":"J. Comput. Syst. Sci."},{"key":"9604_CR12","first-page":"1413","volume":"14","author":"LA Levin","year":"1973","unstructured":"Levin, L.A.: On the notion of a random sequence. Soviet Math. Dokl. 14, 1413\u20131416 (1973)","journal-title":"Soviet Math. Dokl."},{"key":"9604_CR13","first-page":"337","volume":"17","author":"LA Levin","year":"1976","unstructured":"Levin, L.A.: Uniform tests of randomness. Soviet Math. Dokl. 17, 337 (1976)","journal-title":"Soviet Math. Dokl."},{"issue":"6","key":"9604_CR14","doi-asserted-by":"crossref","first-page":"3193","DOI":"10.1090\/S0002-9947-08-04395-X","volume":"360","author":"JS Miller","year":"2008","unstructured":"Miller, J. S., Yu, L.: On initial segment complexity and degrees of randomness. Trans. AMS 360(6), 3193\u20133210 (2008)","journal-title":"Trans. AMS"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9604-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-014-9604-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-014-9604-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:54:27Z","timestamp":1558684467000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-014-9604-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1,27]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9604"],"URL":"https:\/\/doi.org\/10.1007\/s00224-014-9604-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1,27]]}}}