{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T03:19:22Z","timestamp":1775013562079,"version":"3.50.1"},"reference-count":16,"publisher":"Pleiades Publishing Ltd","issue":"1","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Probl Inf Transm"],"published-print":{"date-parts":[[2010,3]]},"DOI":"10.1134\/s0032946010010059","type":"journal-article","created":{"date-parts":[[2010,4,21]],"date-time":"2010-04-21T21:42:26Z","timestamp":1271886146000},"page":"38-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Stability of properties of Kolmogorov complexity under relativization"],"prefix":"10.1134","volume":"46","author":[{"given":"An. A.","family":"Muchnik","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"A. E.","family":"Romashchenko","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"137","published-online":{"date-parts":[[2010,4,23]]},"reference":[{"issue":"6","key":"4069_CR1","first-page":"85","volume":"25","author":"A.K. Zvonkin","year":"1970","unstructured":"Zvonkin, A.K. and Levin, L.A., Complexity of Finite Objects and the Algorithmic Concepts of Information and Randomness, Uspekhi Mat. Nauk, 1970, vol. 25, no. 6, pp. 85\u2013127 [Russian Math. Surveys (Engl. Transl.), 1970, vol. 25, no. 6, pp. 83\u2013124].","journal-title":"Uspekhi Mat. Nauk"},{"key":"4069_CR2","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. and Vit\u00e1nyi, P., An Introduction to Kolmogorov Complexity and Its Applications, New York: Springer, 2008, 3rd ed.","edition":"3rd ed"},{"issue":"1\u20132","key":"4069_CR3","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1016\/S0304-3975(01)00033-0","volume":"271","author":"An.A. Muchnik","year":"2002","unstructured":"Muchnik, An.A., Conditional Complexity and Codes, Theoret. Comput. Sci., 2002, vol. 271, no. 1\u20132, pp. 97\u2013109.","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"4069_CR4","first-page":"149","volume":"2","author":"P. G\u00e1cs","year":"1973","unstructured":"G\u00e1cs, P. and K\u00f6rner, J., Common Information Is Far Less than Mutual Information, Probl. Control Inform. Theory, 1973, vol. 2, no. 2, pp. 149\u2013162.","journal-title":"Probl. Control Inform. Theory"},{"key":"4069_CR5","series-title":"Lect. Notes Comp. Sci.","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1007\/11889342_41","volume-title":"General Theory of Information Transfer and Combinatorics","author":"R. Ahlswede","year":"2006","unstructured":"Ahlswede, R. and K\u00f6rner, J., Appendix: On Common Information and Related Characteristics of Correlated Information Sources, General Theory of Information Transfer and Combinatorics, Ahlswede, R., B\u00e4umer, L., Cai, N., Aydinian, H.K., Blinovsky, V., Deppe, C., and Mashurian, H., Eds., Lect. Notes Comp. Sci., vol. 4123, Berlin: Springer, 2006, pp. 664\u2013677."},{"issue":"2","key":"4069_CR6","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1016\/S0304-3975(98)00070-X","volume":"207","author":"An.A. Muchnik","year":"1998","unstructured":"Muchnik, An.A., On Common Information, Theoret. Comput. Sci., 1998, vol. 207, no. 2, pp. 319\u2013328.","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20132","key":"4069_CR7","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, An.A., Romashchenko, A., Shen, A., and Vereshchagin, N.K., Upper Semi-lattice of Binary Strings with the Relation \u201cx Is Simple Conditional to y,\u201d Theoret. Comput. Sci., 2002, vol. 271, no. 1\u20132, pp. 69\u201395.","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"4069_CR8","first-page":"3","volume":"36","author":"A.E. Romashchenko","year":"2000","unstructured":"Romashchenko, A.E., Pairs of Word with Nonmaterializable Mutual Information, Probl. Peredachi Inf., 2000, vol. 36, no. 1, pp. 3\u201320 [Probl. Inf. Trans. (Engl. Transl.), 2000, vol. 36, no. 1, pp. 1\u201318].","journal-title":"Probl. Peredachi Inf."},{"issue":"3","key":"4069_CR9","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/BF01201280","volume":"29","author":"V.A. Uspensky","year":"1996","unstructured":"Uspensky, V.A. and Shen, A., Relations between Varieties of Kolmogorov Complexities, Math. Syst. Theory, 1996, vol. 29, no. 3, pp. 271\u2013292.","journal-title":"Math. Syst. Theory"},{"issue":"2","key":"4069_CR10","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., Shen, A., and Vereshchagin, N., Inequalities for Shannon Entropy and Kolmogorov Complexity, J. Comput. Syst. Sci., 2000, vol. 60, no. 2, pp. 442\u2013464.","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"4069_CR11","doi-asserted-by":"crossref","first-page":"147","DOI":"10.4310\/CIS.2002.v2.n2.a3","volume":"2","author":"K. Makarychev","year":"2002","unstructured":"Makarychev, K., Makarychev, Yu., Romashchenko, A., and Vereshchagin, N., A New Class of Non-Shannon-type Inequalities for Entropies, Commun. Inf. Syst., 2002, vol. 2, no. 2, pp. 147\u2013162.","journal-title":"Commun. Inf. Syst."},{"issue":"4","key":"4069_CR12","doi-asserted-by":"publisher","first-page":"1440","DOI":"10.1109\/18.681320","volume":"44","author":"Z. Zhang","year":"1998","unstructured":"Zhang, Z., and Yeung, R.W., On Characterization of Entropy Function via Information Inequalities, IEEE Trans. Inform. Theory, 1998, vol. 44, no. 4, pp. 1440\u20131452.","journal-title":"IEEE Trans. Inform. Theory"},{"issue":"6","key":"4069_CR13","first-page":"1337","volume":"271","author":"A.Kh. Shen\u2019","year":"1983","unstructured":"Shen\u2019, A.Kh., The Concept of Kolmogorov (\u03b1, \u03b2)-Stochasticity and Its Properties, Dokl. Akad. Nauk SSSR, 1983, vol. 271, no. 6, pp. 1337\u20131349 [Soviet Math. Doklady (Engl. Transl.), 1983, vol. 28, pp. 295\u2013299].","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"4069_CR14","doi-asserted-by":"crossref","unstructured":"Romashchenko, A., Extracting the Mutual Information for a Triple of Binary Strings, in Proc. 18th IEEE Annual Conf. on Computational Complexity (CCC\u201903), Aarhus, Denmark, 2003, pp. 221\u2013229.","DOI":"10.1109\/CCC.2003.1214422"},{"issue":"1","key":"4069_CR15","first-page":"166","volume":"39","author":"A.E. Romashchenko","year":"2003","unstructured":"Romashchenko, A.E., A Criterion for Extractability of Mutual Information for a Triple of Strings, Probl. Peredachi Inf., 2003, vol. 39, no. 1, pp. 166\u2013175 [Probl. Inf. Trans. (Engl. Transl.), 2003, vol. 39, no. 1, pp. 148\u2013157].","journal-title":"Probl. Peredachi Inf."},{"issue":"1\u20132","key":"4069_CR16","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0304-3975(01)00034-2","volume":"271","author":"A. Romashchenko","year":"2002","unstructured":"Romashchenko, A., Shen, A., and Vereshchagin, N., Combinatorial Interpretation of Kolmogorov Complexity, Theoret. Comput. Sci., 2002, vol. 271, no. 1\u20132, pp. 111\u2013123.","journal-title":"Theoret. Comput. Sci."}],"container-title":["Problems of Information Transmission"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946010010059.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1134\/S0032946010010059","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946010010059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1134\/S0032946010010059.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T02:09:27Z","timestamp":1775009367000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1134\/S0032946010010059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":16,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["4069"],"URL":"https:\/\/doi.org\/10.1134\/s0032946010010059","relation":{},"ISSN":["0032-9460","1608-3253"],"issn-type":[{"value":"0032-9460","type":"print"},{"value":"1608-3253","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"8 June 2009","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 January 2010","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 April 2010","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}