{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T05:07:09Z","timestamp":1740114429226,"version":"3.37.3"},"reference-count":43,"publisher":"Elsevier BV","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2024,2,6]],"date-time":"2024-02-06T00:00:00Z","timestamp":1707177600000},"content-version":"vor","delay-in-days":1466,"URL":"http:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-017"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-012"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-004"}],"funder":[{"DOI":"10.13039\/501100001352","name":"National University of Singapore","doi-asserted-by":"publisher","award":["C252-000-087-001"],"id":[{"id":"10.13039\/501100001352","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001459","name":"Ministry of Education - Singapore","doi-asserted-by":"publisher","award":["MOE2016-T2-1-019\/R146-000-234-112"],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["elsevier.com","sciencedirect.com"],"crossmark-restriction":true},"short-container-title":["Theoretical Computer Science"],"published-print":{"date-parts":[[2020,2]]},"DOI":"10.1016\/j.tcs.2019.10.011","type":"journal-article","created":{"date-parts":[[2019,10,15]],"date-time":"2019-10-15T17:21:16Z","timestamp":1571160076000},"page":"114-127","update-policy":"https:\/\/doi.org\/10.1016\/elsevier_cm_policy","source":"Crossref","is-referenced-by-count":1,"special_numbering":"C","title":["Searching for shortest and least programs"],"prefix":"10.1016","volume":"807","author":[{"given":"Cristian S.","family":"Calude","sequence":"first","affiliation":[]},{"given":"Sanjay","family":"Jain","sequence":"additional","affiliation":[]},{"given":"Wolfgang","family":"Merkle","sequence":"additional","affiliation":[]},{"given":"Frank","family":"Stephan","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1016\/j.tcs.2019.10.011_br0010","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1016\/j.tcs.2005.11.033","article-title":"Computational depth: concept and applications","volume":"354","author":"Antunes","year":"2006","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2019.10.011_br0020","series-title":"The Universal Turing Machine, a Half-Century Survey","first-page":"227","article-title":"Logical depth and physical complexity","author":"Bennett","year":"1988"},{"key":"10.1016\/j.tcs.2019.10.011_br0030","doi-asserted-by":"crossref","first-page":"1575","DOI":"10.1016\/j.jcss.2015.04.004","article-title":"Solovay functions and K-triviality","volume":"81","author":"Bienvenu","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2019.10.011_br0040","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00037-017-0154-2","article-title":"Short lists with short programs in short time","volume":"27","author":"Bauwens","year":"2018","journal-title":"Comput. Complex."},{"issue":"2","key":"10.1016\/j.tcs.2019.10.011_br0050","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1017\/jsl.2014.15","article-title":"Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity","volume":"79","author":"Bauwens","year":"2014","journal-title":"J. Symb. Log."},{"key":"10.1016\/j.tcs.2019.10.011_br0060","series-title":"IEEE 29th Conference on Computational Complexity (CCC)","first-page":"241","article-title":"Linear list-approximation for short programs (or the power of a few random bits)","author":"Bauwens","year":"2014"},{"issue":"2","key":"10.1016\/j.tcs.2019.10.011_br0070","doi-asserted-by":"crossref","first-page":"501","DOI":"10.2178\/jsl\/1146620156","article-title":"Enumerations of the Kolmogorov function","volume":"71","author":"Beigel","year":"2006","journal-title":"J. Symb. Log."},{"key":"10.1016\/j.tcs.2019.10.011_br0080","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/S0019-9958(67)90546-3","article-title":"On the size of machines","volume":"11","author":"Blum","year":"1967","journal-title":"Inf. Control"},{"year":"2002","series-title":"Information and Randomness - An Algorithmic Perspective","author":"Calude","key":"10.1016\/j.tcs.2019.10.011_br0090"},{"issue":"3","key":"10.1016\/j.tcs.2019.10.011_br0100","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1080\/10586458.2002.10504481","article-title":"Computing a glimpse of randomness","volume":"11","author":"Calude","year":"2002","journal-title":"Exp. Math."},{"issue":"4","key":"10.1016\/j.tcs.2019.10.011_br0110","doi-asserted-by":"crossref","first-page":"812","DOI":"10.1016\/j.jcss.2010.08.001","article-title":"Representation of left-computable \u03f5-random reals","volume":"77","author":"Calude","year":"2011","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"10.1016\/j.tcs.2019.10.011_br0120","doi-asserted-by":"crossref","first-page":"479","DOI":"10.1142\/S0129054101000606","article-title":"Coding with minimal programs","volume":"12","author":"Calude","year":"2001","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"22","key":"10.1016\/j.tcs.2019.10.011_br0130","doi-asserted-by":"crossref","first-page":"2253","DOI":"10.1016\/j.tcs.2011.01.002","article-title":"Universal recursively enumerable sets of strings","volume":"412","author":"Calude","year":"2011","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"10.1016\/j.tcs.2019.10.011_br0140","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1016\/0304-3975(76)90005-0","article-title":"Information-theoretic characterizations of recursive infinite strings","volume":"2","author":"Chaitin","year":"1976","journal-title":"Theor. Comput. Sci."},{"year":"2010","series-title":"Algorithmic Randomness and Complexity. Theory and Applications of Computability","author":"Downey","key":"10.1016\/j.tcs.2019.10.011_br0150"},{"key":"10.1016\/j.tcs.2019.10.011_br0160","series-title":"Proceedings of the 7th and 8th Asian Logic Conferences (7th Conference: Hsi-Tou, Taiwan 6 \u2013 10 June 1999, 8th Conference: Chongqing, China 29 August \u2013 2 September 2002)","first-page":"103","article-title":"Trivial reals","author":"Downey","year":"2003"},{"key":"10.1016\/j.tcs.2019.10.011_br0170","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2017.08.010","article-title":"Lowness and logical depth","volume":"702","author":"Downey","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2019.10.011_br0180","doi-asserted-by":"crossref","first-page":"738","DOI":"10.1016\/j.jco.2006.05.001","article-title":"Randomness and universal machines","volume":"22","author":"Figueira","year":"2006","journal-title":"J. Complex."},{"key":"10.1016\/j.tcs.2019.10.011_br0190","doi-asserted-by":"crossref","first-page":"80","DOI":"10.1007\/s00224-012-9413-4","article-title":"Time-bounded Kolmogorov complexity and Solovay functions","volume":"52","author":"H\u00f6lzl","year":"2013","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.tcs.2019.10.011_br0200","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/j.tcs.2017.08.001","article-title":"Enumerations including laconic enumerators","volume":"700","author":"Jain","year":"2017","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2019.10.011_br0210","doi-asserted-by":"crossref","first-page":"37","DOI":"10.1016\/0304-3975(94)00014-X","article-title":"Computational depth and reducibility","volume":"132","author":"Juedes","year":"1994","journal-title":"Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2019.10.011_br0220","doi-asserted-by":"crossref","first-page":"5465","DOI":"10.1090\/S0002-9947-2011-05306-7","article-title":"Kolmogorov complexity and the recursion theorem","volume":"263","author":"Kjos-Hanssen","year":"2011","journal-title":"Trans. Am. Math. Soc."},{"key":"10.1016\/j.tcs.2019.10.011_br0230","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1080\/00207166808803030","article-title":"Three approaches to the quantitative definition of information","volume":"2","author":"Kolmogorov","year":"1968","journal-title":"Int. J. Comput. Math."},{"key":"10.1016\/j.tcs.2019.10.011_br0240","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-49820-1","article-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"Li","year":"2008"},{"key":"10.1016\/j.tcs.2019.10.011_br0250","series-title":"Twenty-Second Annual IEEE Conference on Computational Complexity (CCC 2007)","first-page":"60","article-title":"On C-degrees, H-degrees and T-degrees","author":"Merkle","year":"2007"},{"key":"10.1016\/j.tcs.2019.10.011_br0260","doi-asserted-by":"crossref","first-page":"382","DOI":"10.1016\/S0019-9958(72)90592-X","article-title":"Program size in restricted programming languages","volume":"21","author":"Meyer","year":"1972","journal-title":"Inf. Control"},{"key":"10.1016\/j.tcs.2019.10.011_br0270","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/j.tcs.2012.10.045","article-title":"On the polynomial depth of various sets of random strings","volume":"477","author":"Moser","year":"2013","journal-title":"Theor. Comput. Sci."},{"issue":"4\u20132","key":"10.1016\/j.tcs.2019.10.011_br0280","first-page":"1","article-title":"Depth, highness and DNR degrees","volume":"19","author":"Moser","year":"2017","journal-title":"Discret. Math. Theor. Comput. Sci."},{"key":"10.1016\/j.tcs.2019.10.011_br0290","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/j.ipl.2018.02.015","article-title":"Limit-depth and DNR degrees","volume":"135","author":"Moser","year":"2018","journal-title":"Inf. Process. Lett."},{"year":"2009","series-title":"Computability and Randomness","author":"Nies","key":"10.1016\/j.tcs.2019.10.011_br0300"},{"year":"1989","series-title":"Classical Recursion Theory","author":"Odifreddi","key":"10.1016\/j.tcs.2019.10.011_br0310"},{"year":"1999","series-title":"Classical Recursion Theory, vol. II","author":"Odifreddi","key":"10.1016\/j.tcs.2019.10.011_br0320"},{"key":"10.1016\/j.tcs.2019.10.011_br0330","series-title":"Proceedings of the Ninth Asian Logic Conference, \u201cMathematical Logic in Asia\u201d","first-page":"215","article-title":"Hierarchies of randomness tests","author":"Reimann","year":"2006"},{"year":"1967","series-title":"Theory of Recursive Functions and Effective Computability","author":"Rogers","key":"10.1016\/j.tcs.2019.10.011_br0340"},{"issue":"8","key":"10.1016\/j.tcs.2019.10.011_br0350","doi-asserted-by":"crossref","first-page":"521","DOI":"10.1007\/s001530050112","article-title":"A guided tour of minimal indices and shortest descriptions","volume":"37","author":"Schaefer","year":"1998","journal-title":"Arch. Math. Log."},{"year":"1987","series-title":"Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets","author":"Soare","key":"10.1016\/j.tcs.2019.10.011_br0360"},{"key":"10.1016\/j.tcs.2019.10.011_br0370","first-page":"107","article-title":"Immunity and hyperimmunity for generalized random strings","volume":"49","author":"Stephan","year":"2008","journal-title":"Notre Dame J. Form. Log."},{"issue":"1","key":"10.1016\/j.tcs.2019.10.011_br0380","doi-asserted-by":"crossref","first-page":"291","DOI":"10.2178\/jsl\/1327068704","article-title":"An incomplete set of shortest descriptions","volume":"77","author":"Stephan","year":"2012","journal-title":"J. Symb. Log."},{"issue":"4","key":"10.1016\/j.tcs.2019.10.011_br0390","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/s00037-014-0090-3","article-title":"Short lists for shortest descriptions in short time","volume":"23","author":"Teutsch","year":"2014","journal-title":"Comput. Complex."},{"issue":"4","key":"10.1016\/j.tcs.2019.10.011_br0400","doi-asserted-by":"crossref","DOI":"10.1145\/2799561","article-title":"On approximate decidability of minimal programs","volume":"7","author":"Teutsch","year":"2015","journal-title":"ACM Trans. Comput. Theory"},{"issue":"1","key":"10.1016\/j.tcs.2019.10.011_br0410","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1145\/2902945.2902957","article-title":"A brief on short descriptions","volume":"47","author":"Teutsch","year":"2016","journal-title":"ACM SIGACT News"},{"issue":"4","key":"10.1016\/j.tcs.2019.10.011_br0420","doi-asserted-by":"crossref","first-page":"1440","DOI":"10.1007\/s00224-017-9773-x","article-title":"Short lists with short programs from programs of functions and strings","volume":"61","author":"Vereshchagin","year":"2017","journal-title":"Theory Comput. Syst."},{"key":"10.1016\/j.tcs.2019.10.011_br0430","series-title":"Proceedings of the Tenth CiE. Language, Life, Limits","first-page":"403","article-title":"Short lists with short programs in short time \u2013 a short proof","volume":"vol. 8493","author":"Zimand","year":"2014"}],"container-title":["Theoretical Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397519306401?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0304397519306401?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T16:40:51Z","timestamp":1712421651000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0304397519306401"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2]]},"references-count":43,"alternative-id":["S0304397519306401"],"URL":"https:\/\/doi.org\/10.1016\/j.tcs.2019.10.011","relation":{},"ISSN":["0304-3975"],"issn-type":[{"type":"print","value":"0304-3975"}],"subject":[],"published":{"date-parts":[[2020,2]]},"assertion":[{"value":"Elsevier","name":"publisher","label":"This article is maintained by"},{"value":"Searching for shortest and least programs","name":"articletitle","label":"Article Title"},{"value":"Theoretical Computer Science","name":"journaltitle","label":"Journal Title"},{"value":"https:\/\/doi.org\/10.1016\/j.tcs.2019.10.011","name":"articlelink","label":"CrossRef DOI link to publisher maintained version"},{"value":"article","name":"content_type","label":"Content Type"},{"value":"\u00a9 2019 Elsevier B.V.","name":"copyright","label":"Copyright"}]}}