{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:45Z","timestamp":1753889745386,"version":"3.41.2"},"reference-count":17,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,9,23]],"date-time":"2011-09-23T00:00:00Z","timestamp":1316736000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"National Science Foundation","award":["0554841"],"award-info":[{"award-number":["0554841"]}]},{"name":"National Science Foundation","award":["0532644"],"award-info":[{"award-number":["0532644"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>We investigate the connection between measure, capacity and algorithmic\nrandomness for the space of closed sets. For any computable measure m, a\ncomputable capacity T may be defined by letting T(Q) be the measure of the\nfamily of closed sets K which have nonempty intersection with Q. We prove an\neffective version of Choquet's capacity theorem by showing that every\ncomputable capacity may be obtained from a computable measure in this way. We\nestablish conditions on the measure m that characterize when the capacity of an\nm-random closed set equals zero. This includes new results in classical\nprobability theory as well as results for algorithmic randomness. For certain\ncomputable measures, we construct effectively closed sets with positive\ncapacity and with Lebesgue measure zero. We show that for computable measures,\na real q is upper semi-computable if and only if there is an effectively closed\nset with capacity q.<\/jats:p>","DOI":"10.2168\/lmcs-7(3:16)2011","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T13:45:24Z","timestamp":1415972724000},"source":"Crossref","is-referenced-by-count":0,"title":["Algorithmic Randomness and Capacity of Closed Sets"],"prefix":"10.46298","volume":"Volume 7, Issue 3","author":[{"given":"Douglas","family":"Cenzer","sequence":"first","affiliation":[]},{"given":"Paul","family":"Brodhead","sequence":"additional","affiliation":[]},{"given":"Ferit","family":"Toska","sequence":"additional","affiliation":[]},{"given":"Sebastian","family":"Wyman","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2011,9,23]]},"reference":[{"key":"10.2168\/LMCS-7(3:16)2011_Ax10","unstructured":"L. Axon.Algorithmically Random Closed Sets and Probability.Ph. D. Dissertation, Notre Dame University (2010)."},{"key":"10.2168\/LMCS-7(3:16)2011_BCRW08","doi-asserted-by":"crossref","unstructured":"G. Barmpalias, P. Brodhead, D. Cenzer, J.B. Remmel. R. Weber, Algorithmic Randomness of Continuous Functions.Archive for Mathematical Logic46: 533-546, 2008.","DOI":"10.1007\/s00153-007-0060-4"},{"key":"10.2168\/LMCS-7(3:16)2011_BC10","doi-asserted-by":"crossref","unstructured":"P. Brodhead and D. Cenzer. Effective capacity and randomness of closed sets.Computability and Complexity in Analysis, CCA 2010, eds. X. Zheng and N. Zhong, Springer Electronic Proceedings in Theoretical Computer Science 24: 67-76, 2010.","DOI":"10.4204\/EPTCS.24.11"},{"key":"10.2168\/LMCS-7(3:16)2011_BCDW07","doi-asserted-by":"crossref","first-page":"1041","DOI":"10.1093\/logcom\/exm033","volume":"17","author":"G. Barmpalias, P. Brodhead, D. Cenzer,","year":"2007","journal-title":"J. Logic andComputation"},{"key":"10.2168\/LMCS-7(3:16)2011_CR99","unstructured":"D. Cenzer and J. B. Remmel.Pi01classes.Handbook of Recursive Mathematics, Vol. 2: Recursive Algebra, Analysis and Combinatorics, editors Y. Ersov, S. Goncharov, V. Marek, A. Nerode, J. Remmel. Elsevier Studies in Logic and the Foundations of Mathematics, Vol. 139: 623-821, 1998."},{"key":"10.2168\/LMCS-7(3:16)2011_Ch55","doi-asserted-by":"crossref","first-page":"131","DOI":"10.5802\/aif.53","volume":"5","author":"G. Choquet","year":"1955","journal-title":"Ann. Inst. Fourier"},{"key":"10.2168\/LMCS-7(3:16)2011_D77","first-page":"34","volume":"581","author":"C. Dellacheries","year":"1977","journal-title":"Seminaire de Probabilities XI, Universit\u00e9 de Strasbourg}, Springer Lecture Notes in Mathematics, vol. 581:34-46, 1977"},{"key":"10.2168\/LMCS-7(3:16)2011_DH:book","doi-asserted-by":"crossref","unstructured":"R. Downey and D. Hirschfeldt.Algorithmic Randomness and Complexity. Springer-Verlag, 2010.","DOI":"10.1007\/978-0-387-68441-3"},{"key":"10.2168\/LMCS-7(3:16)2011_GMW88","doi-asserted-by":"crossref","unstructured":"S. Graf, R.D. Mauldin and S.C. Williams. The exact Hausdorff dimension in random recursive constructions.Memoirs Amer. Math. Soc.381:x+121, 1988.","DOI":"10.1090\/memo\/0381"},{"key":"10.2168\/LMCS-7(3:16)2011_KH09","doi-asserted-by":"crossref","first-page":"103","DOI":"10.4310\/MRL.2009.v16.n1.a10","volume":"16","author":"B. Kjos-Hanssen","year":"2009","journal-title":"Math. Research Letters"},{"key":"10.2168\/LMCS-7(3:16)2011_DK09","first-page":"144","volume":"5635","author":"D. Diamondstone and B. Kjos-Hanssen","year":"2009","journal-title":"Mathematical Theory and Computational Practice, CIE 2009, eds. K. Ambos-Spies, B. Loewe and W. Merkle."},{"key":"10.2168\/LMCS-7(3:16)2011_Ma75","unstructured":"G. Matheron.Random Sets and Integral Geometry. John Wiley and Sons, 1975."},{"key":"10.2168\/LMCS-7(3:16)2011_MM09","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s00153-009-0126-6","volume":"48","author":"A. McLinden and R.D. Mauldin","year":"2009","journal-title":"Archive for Math. Logic"},{"key":"10.2168\/LMCS-7(3:16)2011_Ng06","unstructured":"H. T. Nguyen.An Introduction to Random Sets. Chapman and Hall, 2006. A. Nies.Computability and Randomness. Oxford University Press, 2009."},{"key":"10.2168\/LMCS-7(3:16)2011_RSta","unstructured":"J. Reimann and T. Slaman. Measures and their random reals. submitted for publication."},{"key":"10.2168\/LMCS-7(3:16)2011_Rob44","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1214\/aoms\/1177731315","volume":"15","author":"H.E. Robbins","year":"1944","journal-title":"Ann. Math. Statistics"},{"key":"10.2168\/LMCS-7(3:16)2011_Sh76","doi-asserted-by":"crossref","unstructured":"G. Shafer.A Mathematical Theory of EvidencePrinceton University Press, 1976.","DOI":"10.1515\/9780691214696"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/1020\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/1020\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:01:25Z","timestamp":1681243285000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/1020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,9,23]]},"references-count":17,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(3:16)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1106.2993","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1106.2993","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,9,23]]},"article-number":"1020"}}