{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T04:21:52Z","timestamp":1742962912001,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642207112"},{"type":"electronic","value":"9783642207129"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-20712-9_9","type":"book-chapter","created":{"date-parts":[[2011,6,11]],"date-time":"2011-06-11T00:05:22Z","timestamp":1307750722000},"page":"105-119","source":"Crossref","is-referenced-by-count":1,"title":["Kolmogorov Complexity as a Language"],"prefix":"10.1007","author":[{"given":"Alexander","family":"Shen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"1","key":"9_CR1","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.ejc.2005.08.002","volume":"28","author":"N. Alon","year":"2007","unstructured":"Alon, N., Newman, I., Shen, A., Tardos, G., Vereshchagin, N.K.: Partitioning multi-dimensional sets in a small number of \u201cuniform\u201d parts. European Journal of Combinatorics\u00a028(1), 134\u2013144 (2007)","journal-title":"European Journal of Combinatorics"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-10230-1_17","volume-title":"Information Theoretic Security","author":"L. Antunes","year":"2009","unstructured":"Antunes, L., Laplante, S., Pinto, A., Salvador, L.: Cryptographic Security of Individual Instances. In: Desmedt, Y. (ed.) ICITS 2007. LNCS, vol.\u00a04883, pp. 195\u2013210. Springer, Heidelberg (2009)"},{"key":"9_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0304-3975(99)00159-0","volume":"255","author":"C.S. Calude","year":"2001","unstructured":"Calude, C.S., Hertling, P.H., Khoussainov, B., Wang, Y.: Recursively Enumerable Reals and Chaitin $\\mathrm\\Omega$ Numbers. Theoretical Computer Science\u00a0255, 125\u2013149 (2001)","journal-title":"Theoretical Computer Science"},{"issue":"7","key":"9_CR4","doi-asserted-by":"publisher","first-page":"1992","DOI":"10.1109\/TIT.2002.1013138","volume":"48","author":"T.H. Chan","year":"2002","unstructured":"Chan, T.H., Yeung, R.W.: On a relation between information inequalities and group theory. IEEE Transaction on Information theory\u00a048(7), 1992\u20131995 (2002)","journal-title":"IEEE Transaction on Information theory"},{"issue":"1-2","key":"9_CR5","doi-asserted-by":"publisher","first-page":"69","DOI":"10.1016\/S0304-3975(01)00032-9","volume":"271","author":"A. Chernov","year":"2002","unstructured":"Chernov, A., Muchnik, A.A., Romashchenko, A.E., Shen, A., Vereshchagin, N.K.: Upper semi-lattice of binary strings with the relation \u201cx is simple conditional to y\u201d. Theoretical Computer Science\u00a0271(1-2), 69\u201395 (2002)","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"9_CR6","doi-asserted-by":"publisher","first-page":"593","DOI":"10.2178\/jsl\/1208359062","volume":"73","author":"B. Durand","year":"2007","unstructured":"Durand, B., Levin, L.A., Shen, A.: Complex Tilings. Journal of Symbolic Logic\u00a073(2), 593\u2013613 (2007)","journal-title":"Journal of Symbolic Logic"},{"issue":"2","key":"9_CR7","first-page":"119","volume":"2","author":"P. G\u00e1cs","year":"1973","unstructured":"G\u00e1cs, P., Korner, J.: Common Information is Far Less Than Mutual Information. Problems of Control and Information Theory\u00a02(2), 119\u2013162 (1973)","journal-title":"Problems of Control and Information Theory"},{"key":"9_CR8","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1006\/jcss.1999.1677","volume":"60","author":"D. Hammer","year":"2000","unstructured":"Hammer, D., Romashchenko, A.E., Shen, A., Vereshchagin, N.: Inequalities for Shannon Entropy and Kolmogorov Complexity. Journal for Computer and System Sciences\u00a060, 442\u2013464 (2000)","journal-title":"Journal for Computer and System Sciences"},{"issue":"1","key":"9_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s002240000038","volume":"31","author":"D. Hammer","year":"1998","unstructured":"Hammer, D., Shen, A.: A Strange Application of Kolmogorov Complexity. Theory of Computing Systems\u00a031(1), 1\u20134 (1998)","journal-title":"Theory of Computing Systems"},{"key":"9_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"153","DOI":"10.1007\/978-3-642-10631-6_17","volume-title":"Algorithms and Computation","author":"K.A. Hansen","year":"2009","unstructured":"Hansen, K.A., Lachish, O., Miltersen, P.B.: Hilbert\u2019s Thirteenth Problem and Circuit Complexity. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol.\u00a05878, pp. 153\u2013162. Springer, Heidelberg (2009)"},{"issue":"1","key":"9_CR11","first-page":"3","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the definition of the concept \u201cquantity of information\u201d. Problemy Peredachi Informatsii\u00a01(1), 3\u201311 (1965) (Russian)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"11","key":"9_CR12","first-page":"1454","volume":"75","author":"S. Kritchman","year":"2010","unstructured":"Kritchman, S., Raz, R.: The Surprise Examination Paradox and the Second Incompleteness Theorem. Notices of the AMS\u00a075(11), 1454\u20131458 (2010)","journal-title":"Notices of the AMS"},{"issue":"1","key":"9_CR13","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.A.: Randomness and recursive enumerability. SIAM Journal on Computing\u00a031(1), 199\u2013211 (2001)","journal-title":"SIAM Journal on Computing"},{"key":"9_CR14","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., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer, Heidelberg (2008)","edition":"3"},{"issue":"1-2","key":"9_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(01)00033-0","volume":"271","author":"A. Muchnik","year":"2002","unstructured":"Muchnik, A.: Conditional complexity and codes. Theoretical Computer Science\u00a0271(1-2), 97\u2013109 (2002)","journal-title":"Theoretical Computer Science"},{"key":"9_CR16","volume-title":"Theory of Recursive Functions and Effective Computability","author":"H. Rogers Jr.","year":"1967","unstructured":"Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. McGraw-Hill Book Company, New York (1967)"},{"key":"9_CR17","doi-asserted-by":"crossref","unstructured":"Romashchenko, A.E.: A Criterion of Extractability of Mutual Information for a Triple of Strings. Problems of Information Transmission\u00a039(1), 148\u2013157","DOI":"10.1023\/A:1023690701161"},{"issue":"1-2","key":"9_CR18","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0304-3975(01)00034-2","volume":"271","author":"A.E. Romashchenko","year":"2002","unstructured":"Romashchenko, A.E., Shen, A., Vereshchagin, N.K.: Combinatorial Interpretation of Kolmogorov Complexity. Theoretical Computer Science\u00a0271(1-2), 111\u2013123 (2002)","journal-title":"Theoretical Computer Science"},{"key":"9_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"396","DOI":"10.1007\/11672142_32","volume-title":"STACS 2006","author":"A.Y.. Rumyantsev","year":"2006","unstructured":"Rumyantsev, A.Y., Ushakov, M.A.: Forbidden substrings, kolmogorov complexity and almost periodic sequences. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 396\u2013407. Springer, Heidelberg (2006), arxiv.org\/abs\/1009.4455"},{"key":"9_CR20","unstructured":"Shen, A.: Algorithmic Information theory and Kolmogorov complexity. Uppsala university Technical Report TR2000-034, www.it.uu.se\/research\/publications\/reports\/2000-034\/2000-034-nc.ps.gz"},{"key":"9_CR21","unstructured":"Shen, A.: Decomposition complexity. Journ\u00e9es Automates Cellulaires (Turku), 203\u2013213 (2010), hal-00541921 at archives-ouvertes.fr"},{"issue":"3","key":"9_CR22","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1142\/S0129054110007271","volume":"21","author":"Y.-W. Ti","year":"2010","unstructured":"Ti, Y.-W., Chang, C.-L., Lyuu, Y.-D., Shen, A.: Sets of k-independent strings. International Journal of Foundations of Computer Science\u00a021(3), 321\u2013327 (2010)","journal-title":"International Journal of Foundations of Computer Science"}],"container-title":["Lecture Notes in Computer Science","Computer Science \u2013 Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-20712-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,11]],"date-time":"2019-06-11T12:56:31Z","timestamp":1560257791000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-20712-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642207112","9783642207129"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-20712-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}