{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,4]],"date-time":"2025-10-04T14:36:58Z","timestamp":1759588618779},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,11,28]],"date-time":"2007-11-28T00:00:00Z","timestamp":1196208000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2009,6]]},"DOI":"10.1007\/s00224-007-9095-5","type":"journal-article","created":{"date-parts":[[2007,11,27]],"date-time":"2007-11-27T14:08:26Z","timestamp":1196172506000},"page":"150-161","source":"Crossref","is-referenced-by-count":19,"title":["Sophistication Revisited"],"prefix":"10.1007","volume":"45","author":[{"given":"Lu\u00eds","family":"Antunes","sequence":"first","affiliation":[]},{"given":"Lance","family":"Fortnow","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2007,11,28]]},"reference":[{"issue":"3","key":"9095_CR1","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.: Computational depth: Concept and applications. Theor. Comput. Sci. 354(3), 391\u2013404 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"9095_CR2","first-page":"227","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"C.H. 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, London (1988)"},{"issue":"4","key":"9095_CR3","doi-asserted-by":"crossref","first-page":"145","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), 145\u2013149 (1966)","journal-title":"J. ACM"},{"key":"9095_CR4","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1007\/978-94-009-5113-6_2","volume-title":"The Impact of Processing Techniques on Communications","author":"T.M. Cover","year":"1985","unstructured":"Cover, T.M.: Kolmogorov complexity, data compression, and inference. In: Skwirzynski, J.K. (ed.) The Impact of Processing Techniques on Communications, pp. 23\u201333. Nijhoff, Dordrecht (1985)"},{"key":"9095_CR5","doi-asserted-by":"crossref","first-page":"52","DOI":"10.1016\/S0019-9958(82)80085-5","volume":"52","author":"R. Daley","year":"1982","unstructured":"Daley, R.: Busy beaver sets: characterizations and applications. Inf. Control 52, 52\u201367 (1982)","journal-title":"Inf. Control"},{"issue":"6","key":"9095_CR6","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. Inf. Theory 47(6), 2443\u20132463 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"9095_CR7","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Probl. Inf. Transm. 1(1), 1\u20137 (1965)","journal-title":"Probl. Inf. Transm."},{"key":"9095_CR8","first-page":"435","volume-title":"The Universal Turing Machine: A Half-Century Survey","author":"M. Koppel","year":"1988","unstructured":"Koppel, M.: Structure. In: Herken, R. (ed.) The Universal Turing Machine: A Half-Century Survey, pp. 435\u2013452. Oxford University Press, London (1988)"},{"key":"9095_CR9","first-page":"85","volume":"7","author":"M. Koppel","year":"1991","unstructured":"Koppel, M.: Learning to predict non-deterministically generated strings. Mach. Learn. 7, 85\u201399 (1991)","journal-title":"Mach. Learn."},{"key":"9095_CR10","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, 23\u201333 (1991)","journal-title":"Inf. Sci."},{"key":"9095_CR11","first-page":"265","volume":"9","author":"L. Levin","year":"1973","unstructured":"Levin, L.: Universal search problems. Probl. Inf. Transm. 9, 265\u2013266 (1973)","journal-title":"Probl. Inf. Transm."},{"key":"9095_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2606-0","volume-title":"An Introduction to Kolmogorov Complexity and its Applications","author":"M. Li","year":"1997","unstructured":"Li, M., Vit\u00e1nyi, P.: An Introduction to Kolmogorov Complexity and its Applications, 2nd edn. Springer, Berlin (1997)","edition":"2"},{"key":"9095_CR13","first-page":"295","volume":"28","author":"A. Shen","year":"1983","unstructured":"Shen, A.: The concept of (\u03b1,\u03b2)-stochasticity in the Kolmogorov sense, and its properties. Sov. Math. Dokl. 28, 295\u2013299 (1983)","journal-title":"Sov. Math. Dokl."},{"issue":"1","key":"9095_CR14","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"},{"key":"9095_CR15","doi-asserted-by":"crossref","unstructured":"Vereshchagin, N., Vit\u00e1nyi, P.: Kolmogorov\u2019s structure functions and an application to the foundations of model selection. In: Proc. 47th IEEE Symp. Found. Comput. Sci. (2002)","DOI":"10.1109\/SFCS.2002.1182000"},{"issue":"10","key":"9095_CR16","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\u20134627 (2006)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"9095_CR17","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1093\/comjnl\/42.4.294","volume":"42","author":"V.V. 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."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9095-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-007-9095-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-007-9095-5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T07:51:35Z","timestamp":1558684295000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-007-9095-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,11,28]]},"references-count":17,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,6]]}},"alternative-id":["9095"],"URL":"https:\/\/doi.org\/10.1007\/s00224-007-9095-5","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,11,28]]}}}