{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,5]],"date-time":"2025-11-05T00:02:12Z","timestamp":1762300932719,"version":"3.41.2"},"reference-count":1,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2014,12,24]],"date-time":"2014-12-24T00:00:00Z","timestamp":1419379200000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"name":"National Science Foundation","award":["1213151"],"award-info":[{"award-number":["1213151"]}]},{"name":"National Science Foundation","award":["1101228"],"award-info":[{"award-number":["1101228"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>This paper defines a new notion of bounded computable randomness for certain\nclasses of sub-computable functions which lack a universal machine. In\nparticular, we define such versions of randomness for primitive recursive\nfunctions and for PSPACE functions. These new notions are robust in that there\nare equivalent formulations in terms of (1) Martin-L\\\"of tests, (2) Kolmogorov\ncomplexity, and (3) martingales. We show these notions can be equivalently\ndefined with prefix-free Kolmogorov complexity. We prove that one direction of\nvan Lambalgen's theorem holds for relative computability, but the other\ndirection fails. We discuss statistical properties of these notions of\nrandomness.<\/jats:p>","DOI":"10.2168\/lmcs-10(4:15)2014","type":"journal-article","created":{"date-parts":[[2015,5,18]],"date-time":"2015-05-18T07:32:47Z","timestamp":1431934367000},"source":"Crossref","is-referenced-by-count":0,"title":["Sub-computable Boundedness Randomness"],"prefix":"10.46298","volume":"Volume 10, Issue 4","author":[{"given":"Sam","family":"Buss","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Douglas","family":"Cenzer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jeffrey B.","family":"Remmel","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2014,12,24]]},"reference":[{"key":"966:not-found"}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/979\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/979\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T20:00:40Z","timestamp":1681243240000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/979"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,24]]},"references-count":1,"URL":"https:\/\/doi.org\/10.2168\/lmcs-10(4:15)2014","relation":{"is-same-as":[{"id-type":"arxiv","id":"1411.3995","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1411.3995","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2014,12,24]]},"article-number":"979"}}