{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:40:11Z","timestamp":1745944811277,"version":"3.40.4"},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642357213"},{"type":"electronic","value":"9783642357220"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-35722-0_8","type":"book-chapter","created":{"date-parts":[[2013,1,4]],"date-time":"2013-01-04T11:16:29Z","timestamp":1357298189000},"page":"104-118","source":"Crossref","is-referenced-by-count":1,"title":["Sub-computable Bounded Pseudorandomness"],"prefix":"10.1007","author":[{"given":"Douglas","family":"Cenzer","sequence":"first","affiliation":[]},{"given":"Jeffrey B.","family":"Remmel","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"8_CR1","doi-asserted-by":"crossref","unstructured":"Allender, E., Strauss, M.: Measure on small complexity classes with applications for BPP. In: Proceedings of the 35th Symposium on Foundations of Computer Science, pp. 807\u2013818. IEEE Computer Society (1994)","DOI":"10.1109\/SFCS.1994.365713"},{"key":"8_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1007\/3-540-60246-1_119","volume-title":"Mathematical Foundations of Computer Science 1995","author":"E. Allender","year":"1995","unstructured":"Allender, E., Strauss, M.: Measure on P: Robustness of the Notion. In: H\u00e1jek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol.\u00a0969, pp. 129\u2013138. Springer, Heidelberg (1995)"},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"Ambos-Spies, K., Mayordomo, E.: Resource-bounded measure and randomness. In: Sorbi, A. (ed.) Complexity, Logic and Recursion Theory. Lecture Notes in Pure and Applied Mathematics, pp. 1\u201347. Marcel Dekker, New York (1997)","DOI":"10.1201\/9780429187490-1"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.1093\/logcom\/exm033","volume":"17","author":"G. Barmpalias","year":"2007","unstructured":"Barmpalias, G., Brodhead, P., Cenzer, D., Dashti, S., Weber, R.: Algorithmic randomness of closed sets. J. Logic and Computation\u00a017, 1041\u20131062 (2007)","journal-title":"J. Logic and Computation"},{"key":"8_CR5","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1007\/s00153-007-0060-4","volume":"46","author":"G. Barmpalias","year":"2008","unstructured":"Barmpalias, G., Brodhead, P., Cenzer, D., Remmel, J.B., Weber, R.: Algorithmic Randomness of Continuous Functions. Archive for Mathematical Logic\u00a046, 533\u2013546 (2008)","journal-title":"Archive for Mathematical Logic"},{"key":"8_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1007\/978-3-540-73420-8_56","volume-title":"Automata, Languages and Programming","author":"L. Bienvenu","year":"2007","unstructured":"Bienvenu, L., Merkle, W.: Reconciling Data Compression and Kolmogorov Complexity. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol.\u00a04596, pp. 643\u2013654. Springer, Heidelberg (2007)"},{"key":"8_CR7","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1137\/0213053","volume":"13","author":"M. Blum","year":"1984","unstructured":"Blum, M., Micali, S.: How to Generate Cryptographically Strong Sequences of Pseudorandom Bits. Siam J. Computing\u00a013, 850\u2013864 (1984)","journal-title":"Siam J. Computing"},{"key":"8_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/978-3-642-27654-5_5","volume-title":"Computation, Physics and Beyond","author":"P. Brodhead","year":"2012","unstructured":"Brodhead, P., Downey, R., Ng, K.M.: Bounded Randomness. In: Dinneen, M.J., Khoussainov, B., Nies, A. (eds.) WTCS 2012 (Calude Festschrift). LNCS, vol.\u00a07160, pp. 59\u201370. Springer, Heidelberg (2012)"},{"issue":"3","key":"8_CR9","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1137\/S0097539797317123","volume":"31","author":"H. Buhrman","year":"2002","unstructured":"Buhrman, H., Longpre, L.: Compressibility and resource bounded measure. SIAM Journal on Computing\u00a031(3), 876\u2013886 (2002)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR10","doi-asserted-by":"publisher","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. Assoc. Comp. Mach.\u00a013, 547\u2013569 (1966)","journal-title":"J. Assoc. Comp. Mach."},{"key":"8_CR11","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-540-87987-9_15","volume-title":"Algorithmic Learning Theory","author":"A. Chernov","year":"2008","unstructured":"Chernov, A., Shen, A., Vereshchagin, N., Vovk, V.: On-Line Probability, Complexity and Randomness. In: Freund, Y., Gy\u00f6rfi, L., Tur\u00e1n, G., Zeugmann, T. (eds.) ALT 2008. LNCS (LNAI), vol.\u00a05254, pp. 138\u2013153. Springer, Heidelberg (2008)"},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1090\/S0002-9904-1940-07154-X","volume":"46","author":"A. Church","year":"1940","unstructured":"Church, A.: On the concept of random sequences. Bull. Amer. Math. Soc.\u00a046, 130\u2013135 (1940)","journal-title":"Bull. Amer. Math. Soc."},{"key":"8_CR13","doi-asserted-by":"publisher","first-page":"621","DOI":"10.1145\/321541.321551","volume":"16","author":"R. Paola Di","year":"1969","unstructured":"Di Paola, R.: Random sets in subrecursive hierarchies. J. Assoc. Comp. Mach.\u00a016, 621\u2013630 (1969)","journal-title":"J. Assoc. Comp. Mach."},{"key":"8_CR14","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1016\/j.tcs.2004.03.055","volume":"321","author":"R.G. Downey","year":"2004","unstructured":"Downey, R.G., Griffiths, E.J., Reid, S.: On Kurtz randomness. Theoretical Computer Science\u00a0321, 249\u2013270 (2004)","journal-title":"Theoretical Computer Science"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"Downey, R., Hirschfeldt, D.: Algorithmic Randomness and Complexity. Springer (2011)","DOI":"10.1007\/978-0-387-68441-3"},{"key":"8_CR16","unstructured":"Kautz, S.: Degrees of Random Sets. Ph.D. Thesis, Cornell University (1991)"},{"key":"8_CR17","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1016\/0304-3975(86)90081-2","volume":"48","author":"K. Ko","year":"1986","unstructured":"Ko, K.: On the notion of infinite pseudorandom sequences. Theoretical Computer Science\u00a048, 9\u201333 (1986)","journal-title":"Theoretical Computer Science"},{"key":"8_CR18","first-page":"1","volume":"1","author":"A.N. Kolmogorov","year":"1965","unstructured":"Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Problems of Information Transmission\u00a01, 1\u20137 (1965)","journal-title":"Problems of Information Transmission"},{"key":"8_CR19","unstructured":"Kurtz, S.: Randomness and Genericity in the Degrees of Unsolvability. Ph.D. Thesis, University of Illinois at Urbana (1981)"},{"key":"8_CR20","first-page":"1413","volume":"14","author":"L. Levin","year":"1973","unstructured":"Levin, L.: On the notion of a random sequence. Soviet Math. Doklady\u00a014, 1413\u20131416 (1973)","journal-title":"Soviet Math. Doklady"},{"key":"8_CR21","doi-asserted-by":"crossref","unstructured":"Li, M., Vitanyi, P.: An introduction to Kolmogorov Complexity and Its Applications, 3rd edn. Springer (2008)","DOI":"10.1007\/978-0-387-49820-1"},{"key":"8_CR22","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J.H. Lutz","year":"1990","unstructured":"Lutz, J.H.: Category and measure in complexity classes. SIAM Journal on Computing\u00a019, 1100\u20131131 (1990)","journal-title":"SIAM Journal on Computing"},{"key":"8_CR23","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/malq.200910128","volume":"57","author":"K. Miyabe","year":"2011","unstructured":"Miyabe, K.: Truth-table Schnorr randomness and truth-table reducible randomness. Math. Logic Quarterly\u00a057, 323\u2013338 (2011)","journal-title":"Math. Logic Quarterly"},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"602","DOI":"10.1016\/S0019-9958(66)80018-9","volume":"9","author":"P. Martin-L\u00f6f","year":"1966","unstructured":"Martin-L\u00f6f, P.: The definition of random sequences. Information and Control\u00a09, 602\u2013619 (1966)","journal-title":"Information and Control"},{"key":"8_CR25","doi-asserted-by":"crossref","unstructured":"Nies, A.: Computability and Randomness. Oxford University Press (2009)","DOI":"10.1093\/acprof:oso\/9780199230761.001.0001"},{"key":"8_CR26","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/BF01694181","volume":"5","author":"C.P. Schnorr","year":"1971","unstructured":"Schnorr, C.P.: A unified approach to the definition of random sequences. Mathematical Systems Theory\u00a05, 246\u2013258 (1971)","journal-title":"Mathematical Systems Theory"},{"key":"8_CR27","unstructured":"Ville, J.: \u00c9tude Critique de la Notion de Collectif. Gauthier-Villars, Paris (1939)"},{"key":"8_CR28","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1016\/S0304-3975(98)00119-4","volume":"237","author":"Y. Wang","year":"2000","unstructured":"Wang, Y.: Resource bounded randomness and computational complexity. Theoretical Computer Science\u00a0237, 33\u201355 (2000)","journal-title":"Theoretical Computer Science"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"Wilber, R.: Randomness and the density of hard problems. In: Proc. 24th IEEE Symposium on Foundations of Computer Science, pp. 335\u2013342 (1983)","DOI":"10.1109\/SFCS.1983.49"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-35722-0_8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,29]],"date-time":"2025-04-29T16:00:36Z","timestamp":1745942436000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-35722-0_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642357213","9783642357220"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-35722-0_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}