{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,29]],"date-time":"2026-03-29T15:34:32Z","timestamp":1774798472465,"version":"3.50.1"},"publisher-location":"Cham","reference-count":49,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319500614","type":"print"},{"value":"9783319500621","type":"electronic"}],"license":[{"start":{"date-parts":[[2016,12,1]],"date-time":"2016-12-01T00:00:00Z","timestamp":1480550400000},"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":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-50062-1_41","type":"book-chapter","created":{"date-parts":[[2016,11,30]],"date-time":"2016-11-30T10:09:42Z","timestamp":1480500582000},"page":"669-737","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Algorithmic Statistics: Forty Years Later"],"prefix":"10.1007","author":[{"given":"Nikolay","family":"Vereshchagin","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Shen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,12,1]]},"reference":[{"key":"41_CR1","unstructured":"Adleman, L.M.: Time, space and randomness. MIT report MIT\/LCS\/TM-131, March 1979"},{"key":"41_CR2","doi-asserted-by":"publisher","unstructured":"Antunes, L., Bauwens, B., Souto, A., Teixeira, A.: Sophistication vs. logical depth. Theory of Computing Systems. doi:10.1007\/s00224-016-9672-6","DOI":"10.1007\/s00224-016-9672-6"},{"issue":"1","key":"41_CR3","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/s00224-007-9095-5","volume":"45","author":"L Antunes","year":"2009","unstructured":"Antunes, L., Fortnow, L.: Sophistication revisited. Theory Comput. Syst. 45(1), 150\u2013161 (2009)","journal-title":"Theory Comput. Syst."},{"key":"41_CR4","doi-asserted-by":"crossref","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D.: Computational depth, In: Proceedings of the 16th IEEE Conference on Computational Complexity, pp. 266\u2013273. IEEE, New York (2001). Journal version: Computational depth: concept and applications. Theoret. Comput. Sci. 354(3), 391\u2013404 (2006)","DOI":"10.1016\/j.tcs.2005.11.033"},{"issue":"4","key":"41_CR5","doi-asserted-by":"publisher","first-page":"724","DOI":"10.1007\/s00224-009-9171-0","volume":"45","author":"L Antunes","year":"2009","unstructured":"Antunes, L., Matos, A., Souto, A., Vit\u00e1nyi, P.: Depth as randomness deficiency. Theory Comput. Syst. 45(4), 724\u2013739 (2009)","journal-title":"Theory Comput. Syst."},{"key":"41_CR6","unstructured":"Bauwens, B.: Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity. Ph.D. thesis, University of Gent, May 2010"},{"key":"41_CR7","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"CH Bennett","year":"1988","unstructured":"Bennett, C.H.: Logical depth and physical complexity. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 227\u2013257. Oxford University Press, New York (1988)"},{"key":"41_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-3-662-47672-7_18","volume-title":"Automata, Languages, and Programming","author":"L Bienvenu","year":"2015","unstructured":"Bienvenu, L., Desfontaines, D., Shen, A.: What percentage of programs halt? In: Halld\u00f3rsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015. LNCS, vol. 9134, pp. 219\u2013230. Springer, Heidelberg (2015). doi:10.1007\/978-3-662-47672-7_18"},{"key":"41_CR9","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1134\/S0081543811060058","volume":"274","author":"L Bienvenu","year":"2011","unstructured":"Bienvenu, L., G\u00e1cs, P., Hoyrup, M., Rojas, C., Shen, A.: Algorithmic tests and randomness with respect to a class of measures. Proc. Steklov Inst. Math. 274, 34\u201389 (2011)","journal-title":"Proc. Steklov Inst. Math."},{"key":"41_CR10","series-title":"NATO ASI Series","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/978-94-009-5113-6_2","volume-title":"The Impact of Processing Techniques on Communications","author":"T Cover","year":"1985","unstructured":"Cover, T.: Kolmogorov complexity, data compression and inference. In: Skwirzynski, J.K. (ed.) The Impact of Processing Techniques on Communications. NATO ASI Series, vol. 91, pp. 23\u201333. Martinus Nijhoff Publishers, Dordrecht (1985). doi:10.1007\/978-94-009-5113-6_2"},{"key":"41_CR11","unstructured":"Epstein, S., Levin, L.: Sets have simple members. http:\/\/arxiv.org\/abs\/1107.1458, reposted as http:\/\/arxiv.org\/abs\/1403.4539"},{"key":"41_CR12","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/0304-3975(83)90139-1","volume":"22","author":"P G\u00e1cs","year":"1983","unstructured":"G\u00e1cs, P.: On the relation between descriptional complexity and algorithmic probability. Theoret. Comput. Sci. 22, 71\u201393 (1983)","journal-title":"Theoret. Comput. Sci."},{"issue":"6","key":"41_CR13","doi-asserted-by":"publisher","first-page":"2443","DOI":"10.1109\/18.945257","volume":"47","author":"P G\u00e1cs","year":"2001","unstructured":"G\u00e1cs, P., Tromp, J., Vit\u00e1nyi, P.M.B.: Algorithmic statistics. IEEE Trans. Inf. Theory 47(6), 2443\u20132463 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"41_CR14","first-page":"4","volume":"1","author":"AN Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information (in Russian). Prob. Inf. Trans. 1(1), 4\u201311 (1965). English translation published: Int. J. Comput. Math. 2, 157\u2013168 (1968)","journal-title":"Prob. Inf. Trans."},{"key":"41_CR15","unstructured":"Kolmogorov, A.N.: Talk at the Information Theory Symposium in Tallinn, Estonia (then USSR) (1974) [As reported by Cover in his 1985 paper [10]]"},{"key":"41_CR16","unstructured":"Kolmogorov, A.N.: The complexity of algorithms and the objective definition of randomness. Summary of the talk presented April 16, 1974 at Moscow Mathematical Society. Uspekhi matematicheskikh nauk (Russian) 29(4[178]), 155 (1974). http:\/\/mi.mathnet.ru\/rus\/umn\/v29\/i4\/p153 (A short note in Russian)"},{"key":"41_CR17","unstructured":"Kolmogorov, A.N.: Talk at the seminar at Moscow State University Mathematics Department (Logic Division), 26 November 1981. [The definition of $$(\\alpha ,\\beta )$$-stochasticity was defined in this talk, and the question about the fraction of non-stochastic objects was posed.]"},{"key":"41_CR18","first-page":"1087","volume":"1","author":"M Koppel","year":"1987","unstructured":"Koppel, M.: Complexity, depth and sophistication. Compl. Syst. 1, 1087\u20131091 (1987)","journal-title":"Compl. Syst."},{"key":"41_CR19","doi-asserted-by":"crossref","unstructured":"Koppel, M.: Structure. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 435\u2013452. Oxford University Press (1988)","DOI":"10.1093\/oso\/9780198537748.003.0019"},{"issue":"1\u20133","key":"41_CR20","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/0020-0255(91)90021-L","volume":"56","author":"M Koppel","year":"1991","unstructured":"Koppel, M., Atlan, H.: An almost machine-independent theory of program-length complexity, sophistication, and induction. Inf. Sci. 56(1\u20133), 23\u201333 (1991)","journal-title":"Inf. Sci."},{"issue":"1","key":"41_CR21","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/S0019-9958(84)80060-1","volume":"61","author":"L Levin","year":"1984","unstructured":"Levin, L.: Randomness conservation inequalities; information and independence in mathematical theories. Inf. Control 61(1), 15\u201337 (1984)","journal-title":"Inf. Control"},{"key":"41_CR22","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.M.B.: An Introduction to Kolmogorov Complexity and its Applications, 3rd edn. Springer, New York (2008)","edition":"3"},{"key":"41_CR23","unstructured":"Longpr\u00e9, L.: Resource bounded Kolmogorov complexity, a link between computational complexity and information theory. Ph.D. Thesis, Department of Computer Science, Cornell University, TR 86\u2013776 (1986)"},{"key":"41_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/978-3-319-20297-6_22","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Milovanov","year":"2015","unstructured":"Milovanov, A.: Some properties of antistochastic strings. In: Beklemishev, L.D., Musatov, D.V. (eds.) CSR 2015. LNCS, vol. 9139, pp. 339\u2013349. Springer, Heidelberg (2015). doi:10.1007\/978-3-319-20297-6_22"},{"key":"41_CR25","doi-asserted-by":"publisher","unstructured":"Milovanov, A.: Algorithmic statistic, prediction and machine learning. In: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016), Leibnitz International Proceedings in Informatics (LIPIcs), vol. 47, pp. 54:1\u201354:13 (2016). doi:10.4230\/LIPIcs.STACS.2016.54, http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2016\/5755\/","DOI":"10.4230\/LIPIcs.STACS.2016.54"},{"key":"41_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-34171-2_20","volume-title":"Computer Science \u2013 Theory and Applications","author":"A Milovanov","year":"2016","unstructured":"Milovanov, A.: Algorithmic statistics: normal objects and universal models. In: Kulikov, A.S., Woeginger, G.J. (eds.) CSR 2016. LNCS, vol. 9691, pp. 280\u2013293. Springer, Heidelberg (2016). doi:10.1007\/978-3-319-34171-2_20"},{"key":"41_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-39310-5_17","volume-title":"Descriptional Complexity of Formal Systems","author":"F Mota","year":"2013","unstructured":"Mota, F., Aaronson, S., Antunes, L., Souto, A.: Sophistication as randomness deficiency. In: Jurgensen, H., Reis, R. (eds.) DCFS 2013. LNCS, vol. 8031, pp. 172\u2013181. Springer, Heidelberg (2013). doi:10.1007\/978-3-642-39310-5_17"},{"key":"41_CR28","unstructured":"Muchnik, An.A., Mezhirov, I., Shen, A., Vereshchagin, N.K.: Game interpretation of Kolmogorov complexity. https:\/\/arxiv.org\/abs\/1003.4712"},{"key":"41_CR29","doi-asserted-by":"crossref","unstructured":"Muchnik, An.A., Romashchenko, A.: Stability of properties of Kolmogorov complexity under relativization. Prob. Inf. Trans. 46(1), 38\u201361 (2010)","DOI":"10.1134\/S0032946010010059"},{"key":"41_CR30","doi-asserted-by":"crossref","unstructured":"Muchnik, An.A., Semenov, A.L., Uspensky, V.A.: Mathematical metaphysics of randomness. Theoret. Comput. Sci. 207(2), 263\u2013317 (1998)","DOI":"10.1016\/S0304-3975(98)00069-3"},{"key":"41_CR31","unstructured":"Muchnik, An.A., Shen, A., Vyugin, M.: Game arguments in computability theory and algorithmic information theory. https:\/\/arxiv.org\/pdf\/1204.0198.pdf"},{"issue":"3","key":"41_CR32","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1109\/TC.2011.25","volume":"61","author":"S de Rooij","year":"2012","unstructured":"de Rooij, S., Vit\u00e1nyi, P.M.B.: Approximating rate-distortion graphs of individual data: experiments in lossy compression and denoising. IEEE Trans. Comput. 61(3), 395\u2013407 (2012)","journal-title":"IEEE Trans. Comput."},{"key":"41_CR33","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1016\/0005-1098(78)90005-5","volume":"14","author":"J Rissanen","year":"1978","unstructured":"Rissanen, J.: Modeling by shortest data description. Automatica 14, 465\u2013471 (1978)","journal-title":"Automatica"},{"issue":"1","key":"41_CR34","first-page":"295","volume":"28","author":"A Shen","year":"1983","unstructured":"Shen, A.: The concept of $$(\\alpha,\\beta )$$-stochasticity in the Kolmogorov sense, and its properties. Soviet Math. Dokl. 28(1), 295\u2013299 (1983)","journal-title":"Soviet Math. Dokl."},{"issue":"4","key":"41_CR35","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1093\/comjnl\/42.4.340","volume":"42","author":"A Shen","year":"1999","unstructured":"Shen, A.: Discussion on Kolmogorov complexity and statistical analysis. Comput. J. 42(4), 340\u2013342 (1999)","journal-title":"Comput. J."},{"key":"41_CR36","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/978-3-319-21852-6_7","volume-title":"Measures of Complexity: Festschrift for Alexey Chervonenkis","author":"A Shen","year":"2015","unstructured":"Shen, A.: Around Kolmogorov complexity: basic notions and results. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity: Festschrift for Alexey Chervonenkis, pp. 75\u2013116. Springer, Switzerland (2015). doi:10.1007\/978-3-319-21852-6_7. arXiv:1504.04955"},{"issue":"1","key":"41_CR37","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0019-9958(64)90223-2","volume":"7","author":"R Solomonoff","year":"1964","unstructured":"Solomonoff, R.: A formal theory of inductive inference. Part I. Inf. Control 7(1), 1\u201322 (1964)","journal-title":"Inf. Control"},{"issue":"2","key":"41_CR38","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1016\/S0019-9958(64)90131-7","volume":"7","author":"R Solomonoff","year":"1964","unstructured":"Solomonoff, R.: A formal theory of inductive inference. Part II. Applications of the systems to various problems in induction. Inf. Control 7(2), 224\u2013254 (1964)","journal-title":"Inf. Control"},{"key":"41_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"478","DOI":"10.1007\/978-3-642-03073-4_49","volume-title":"Mathematical Theory and Computational Practice","author":"N Vereshchagin","year":"2009","unstructured":"Vereshchagin, N.: Algorithmic minimal sufficient statistic revisited. In: Ambos-Spies, K., L\u00f6we, B., Merkle, W. (eds.) CiE 2009. LNCS, vol. 5635, pp. 478\u2013487. Springer, Heidelberg (2009). doi:10.1007\/978-3-642-03073-4_49"},{"issue":"3","key":"41_CR40","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/s00224-014-9605-1","volume":"58","author":"N Vereshchagin","year":"2016","unstructured":"Vereshchagin, N.: Algorithmic minimal sufficient statistics: a new approach. Theory Comput. Syst. 58(3), 463\u2013481 (2016)","journal-title":"Theory Comput. Syst."},{"key":"41_CR41","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-319-21852-6_17","volume-title":"Measures of Complexity: Festschrift for Alexey Chervonenkis","author":"N Vereshchagin","year":"2015","unstructured":"Vereshchagin, N., Shen, A.: Algorithmic statistics revisited. In: Vovk, V., Papadopoulos, H., Gammerman, A. (eds.) Measures of Complexity: Festschrift for Alexey Chervonenkis, pp. 235\u2013252. Springer, Switzerland (2015). arXiv:1504.04950"},{"key":"41_CR42","unstructured":"Vereshchagin, N., Uspensky, V., Shen, A.: Kolmogorov complexity and algorithmic randomness. In: MCCME 2013, 576 pp., Moscow (2013). http:\/\/www.lirmm.fr\/~ashen\/kolmbook.pdf (Russian version), http:\/\/www.lirmm.fr\/~ashen\/kolmbook-eng.pdf (English version)"},{"issue":"12","key":"41_CR43","doi-asserted-by":"publisher","first-page":"3265","DOI":"10.1109\/TIT.2004.838346","volume":"50","author":"NK Vereshchagin","year":"2004","unstructured":"Vereshchagin, N.K., Vit\u00e1nyi, P.M.B.: Kolmogorov\u2019s structure functions and model selection. IEEE Trans. Inf. Theory 50(12), 3265\u20133290 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"7","key":"41_CR44","doi-asserted-by":"publisher","first-page":"3438","DOI":"10.1109\/TIT.2010.2048491","volume":"56","author":"NK Vereshchagin","year":"2010","unstructured":"Vereshchagin, N.K., Vit\u00e1nyi, P.M.B.: Rate distortion and denoising of individual data using Kolmogorov complexity. IEEE Trans. Inf. Theory 56(7), 3438\u20133454 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"10","key":"41_CR45","doi-asserted-by":"publisher","first-page":"4617","DOI":"10.1109\/TIT.2006.881729","volume":"52","author":"PMB Vit\u00e1nyi","year":"2006","unstructured":"Vit\u00e1nyi, P.M.B.: Meaningful information. IEEE Trans. Inf. Theory 52(10), 4617\u20134626 (2006). arXiv:cs\/0111053","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"41_CR46","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1137\/1132071","volume":"32","author":"VV V\u2019yugin","year":"1987","unstructured":"V\u2019yugin, V.V.: On the defect of randomness of a finite object with respect to measures with given complexity bounds. SIAM Theory Prob. Appl. 32(3), 508\u2013512 (1987)","journal-title":"SIAM Theory Prob. Appl."},{"issue":"4","key":"41_CR47","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1093\/comjnl\/42.4.294","volume":"42","author":"VV V\u2019yugin","year":"1999","unstructured":"V\u2019yugin, V.V.: Algorithmic complexity and stochastic properties of finite binary sequences. Comput. J. 42(4), 294\u2013317 (1999)","journal-title":"Comput. J."},{"issue":"1","key":"41_CR48","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1016\/S0304-3975(01)00122-0","volume":"276","author":"VV V\u2019yugin","year":"2002","unstructured":"V\u2019yugin, V.V.: Does snooping help? Theoret. Comput. Sci. 276(1), 407\u2013415 (2002)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"41_CR49","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1093\/comjnl\/11.2.185","volume":"11","author":"CS Wallace","year":"1968","unstructured":"Wallace, C.S., Boulton, D.M.: An information measure for classification. Comput. J. 11(2), 185\u2013194 (1968)","journal-title":"Comput. J."}],"container-title":["Lecture Notes in Computer Science","Computability and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-50062-1_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T16:59:17Z","timestamp":1709830757000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-50062-1_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,1]]},"ISBN":["9783319500614","9783319500621"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-50062-1_41","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,1]]},"assertion":[{"value":"1 December 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}