{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,8,2]],"date-time":"2024-08-02T07:48:10Z","timestamp":1722584890157},"reference-count":31,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,3,19]],"date-time":"2016-03-19T00:00:00Z","timestamp":1458345600000},"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":[[2017,2]]},"DOI":"10.1007\/s00224-016-9672-6","type":"journal-article","created":{"date-parts":[[2016,3,19]],"date-time":"2016-03-19T01:59:44Z","timestamp":1458352784000},"page":"280-298","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Sophistication vs Logical Depth"],"prefix":"10.1007","volume":"60","author":[{"given":"Lu\u00eds","family":"Antunes","sequence":"first","affiliation":[]},{"given":"Bruno","family":"Bauwens","sequence":"additional","affiliation":[]},{"given":"Andr\u00e9","family":"Souto","sequence":"additional","affiliation":[]},{"given":"Andreia","family":"Teixeira","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,3,19]]},"reference":[{"issue":"1","key":"9672_CR1","doi-asserted-by":"crossref","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":"1","key":"9672_CR2","first-page":"3","volume":"1","author":"A Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.: Three approaches to the quantitative definition of information. Problemy Peredachi Informatsii 1(1), 3\u201311 (1965)","journal-title":"Problemy Peredachi Informatsii"},{"issue":"4","key":"9672_CR3","doi-asserted-by":"crossref","first-page":"547","DOI":"10.1145\/321356.321363","volume":"13","author":"G Chaitin","year":"1966","unstructured":"Chaitin, G.: On the length of programs for computing finite binary sequences. J. ACM 13(4), 547\u2013569 (1966). ACM Press","journal-title":"J. ACM"},{"key":"9672_CR4","first-page":"227","volume-title":"Logical Depth and Physical Complexity","author":"C Bennett","year":"1988","unstructured":"Bennett, C.: Logical Depth and Physical Complexity, pp 227\u2013257. Oxford University Press, Inc., New York (1988)"},{"issue":"3","key":"9672_CR5","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/j.tcs.2005.11.033","volume":"354","author":"L Antunes","year":"2006","unstructured":"Antunes, L., Fortnow, L., van Melkebeek, D., Vinodchandran, N.V.: Computational depth: concept and applications. Theor. Comput. Sci. 354(3), 391\u2013404 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9672_CR6","first-page":"1087","volume":"1","author":"M Koppel","year":"1987","unstructured":"Koppel, M.: Complexity, depth, and sophistication. Complex Systems 1, 1087\u20131091 (1987)","journal-title":"Complex Systems"},{"key":"9672_CR7","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0304-3975(94)00014-X","volume":"132","author":"D Juedes","year":"1994","unstructured":"Juedes, D., Lathrop, J., Lutz, J.: Computational depth and reducibility. Theor. Comput. Sci. 132, 37\u201370 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"9672_CR8","unstructured":"Kolmogorov, A.N.: Talk in Information Theory Symposium. In: Tallinn, Estonia (1973)"},{"issue":"4","key":"9672_CR9","first-page":"155","volume":"29","author":"AN Kolmogorov","year":"1974","unstructured":"Kolmogorov, A.N.: Complexity of algorithms and objective definition of randomness. Uspekhi Mat. Nauk 29(4), 155 (1974)","journal-title":"Uspekhi Mat. Nauk"},{"key":"9672_CR10","doi-asserted-by":"crossref","unstructured":"Koppel, M.: Structure. In: Herken, R. (ed.) The Universal Turing Machine: a Half-Century Survey, 2nd edition, pp 403\u2013419. Springer (1995)","DOI":"10.1007\/978-3-7091-6597-3_19"},{"issue":"1-3","key":"9672_CR11","doi-asserted-by":"crossref","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-3), 23\u201333 (1991). Elsevier Science Publishers Ltd.","journal-title":"Inf. Sci."},{"key":"9672_CR12","doi-asserted-by":"crossref","unstructured":"Li, Ming, Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and its Applications. Springer (2008)","DOI":"10.1007\/978-0-387-49820-1"},{"issue":"1","key":"9672_CR13","doi-asserted-by":"crossref","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 of Computing Systems 45(1), 150\u2013161 (2009). Springer","journal-title":"Theory of Computing Systems"},{"key":"9672_CR14","doi-asserted-by":"crossref","first-page":"3265","DOI":"10.1109\/TIT.2004.838346","volume":"50","author":"N Vereshchagin","year":"2004","unstructured":"Vereshchagin, N., Vitanyi, P.: Kolmogorov\u2019s structure functions and model selection. IEEE Trans. Inf. Theory 50, 3265\u20133290 (2004). Computer Society","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9672_CR15","doi-asserted-by":"crossref","unstructured":"Li, Ming, Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and Its Applications. Springer (1997)","DOI":"10.1007\/978-1-4757-2606-0"},{"issue":"3","key":"9672_CR16","doi-asserted-by":"crossref","first-page":"840","DOI":"10.1214\/aop\/1176991250","volume":"17","author":"T Cover","year":"1989","unstructured":"Cover, T., Gacs, P., Gray, R.M.: Kolmogorov\u2019s contributions to information theory and algorithmic complexity. Ann. Probab. 17(3), 840\u2013865 (1989)","journal-title":"Ann. Probab."},{"key":"9672_CR17","unstructured":"Epstein, S., Levin, L.: On sets of high complexity strings. CoRR, arXiv: abs\/1107.1458 (2011)"},{"issue":"1","key":"9672_CR18","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 Mathematics Doklady 28(1), 295\u2013299 (1983)","journal-title":"Soviet Mathematics Doklady"},{"issue":"3","key":"9672_CR19","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1137\/1132071","volume":"32","author":"V Vyugin","year":"1987","unstructured":"Vyugin, V.: On the defect of randomness of a finite object with respect to measures with given complexity bounds. Theory Prob. Appl. 32(3), 508\u2013512 (1987)","journal-title":"Theory Prob. Appl."},{"issue":"6","key":"9672_CR20","doi-asserted-by":"crossref","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.: Algorithmic statistics. IEEE Trans. Inform. Theory 47(6), 2443\u20132463 (2001)","journal-title":"IEEE Trans. Inform. Theory"},{"key":"9672_CR21","doi-asserted-by":"crossref","unstructured":"Cover, T.: The Impact of Processing Techniques on Communications. chapter Kolmogorov Complexity, Data Compression and Inference., pages 23\u201333. J. Skwyrzynski. Martinus Nijhoff Publishers (1985)","DOI":"10.1007\/978-94-009-5113-6_2"},{"key":"9672_CR22","doi-asserted-by":"crossref","unstructured":"Cover, T., Joy, T.: Elements of Information Theory. Wiley (1991)","DOI":"10.1002\/0471200611"},{"issue":"10","key":"9672_CR23","doi-asserted-by":"crossref","first-page":"4617","DOI":"10.1109\/TIT.2006.881729","volume":"52","author":"P Vit\u00e1nyi","year":"2006","unstructured":"Vit\u00e1nyi, P.: Meaningful information. IEEE Trans. Inf. Theory 52(10), 4617\u20134626 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9672_CR24","unstructured":"Shen, A.: Algorithmic statistics: main results. In preparation (2013)"},{"key":"9672_CR25","doi-asserted-by":"crossref","unstructured":"Vereshchagin, N.: Algorithmic minimal sufficient statistic revisited. Mathematical Theory and Computational Practice, 478\u2013487 (2009)","DOI":"10.1007\/978-3-642-03073-4_49"},{"key":"9672_CR26","doi-asserted-by":"crossref","unstructured":"Verschagin, N.: On Algorithmic Strong Sufficient Statistics. In: Proceedings of Computability in Europe (2013)","DOI":"10.1007\/978-3-642-39053-1_50"},{"issue":"1","key":"9672_CR27","doi-asserted-by":"crossref","first-page":"44","DOI":"10.1002\/(SICI)1099-0526(199609\/10)2:1<44::AID-CPLX10>3.0.CO;2-X","volume":"2","author":"M Gell-Mann","year":"1998","unstructured":"Gell-Mann, M., Lloyd, S.: Information measures, effective complexity, and total information. Complexity 2(1), 44\u201352 (1998)","journal-title":"Complexity"},{"key":"9672_CR28","doi-asserted-by":"crossref","unstructured":"Gell-Mann, M., Lloyd, S.: Effective complexity. Nonextensive entropy, 387\u2013398 (2004)","DOI":"10.1093\/oso\/9780195159769.003.0028"},{"issue":"9","key":"9672_CR29","doi-asserted-by":"crossref","first-page":"4593","DOI":"10.1109\/TIT.2010.2053892","volume":"56","author":"A Nihat","year":"2010","unstructured":"Nihat, A., Muller, M., Szkola, A.: Effective complexity and its relation to logical depth. IEEE Trans. Inf. Theory 56(9), 4593\u20134607 (2010)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9672_CR30","unstructured":"Bauwens, B.: Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity. PhD thesis, Ugent (2010)"},{"key":"9672_CR31","unstructured":"Vereshchagin, N., Shen, A.: Algorithmic statistics revisited (2015). arXiv preprint arXiv: 1504.04950"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9672-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-016-9672-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9672-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-016-9672-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,15]],"date-time":"2022-06-15T17:22:16Z","timestamp":1655313736000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-016-9672-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,19]]},"references-count":31,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["9672"],"URL":"https:\/\/doi.org\/10.1007\/s00224-016-9672-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,19]]}}}