{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:17:49Z","timestamp":1725484669527},"publisher-location":"Berlin, Heidelberg","reference-count":43,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540434009"},{"type":"electronic","value":"9783540459958"}],"license":[{"start":{"date-parts":[[2002,1,1]],"date-time":"2002-01-01T00:00:00Z","timestamp":1009843200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45995-2_35","type":"book-chapter","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T22:33:34Z","timestamp":1180478014000},"page":"386-399","source":"Crossref","is-referenced-by-count":0,"title":["Category, Measure, Inductive Inference: A Triality Theorem and Its Applications"],"prefix":"10.1007","author":[{"given":"R\u016bsi\u0146\u0161","family":"Freivalds","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carl H.","family":"Smith","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,3,14]]},"reference":[{"key":"35_CR1","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/3-540-60922-9_21","volume-title":"General inductive inference types based on linearly ordered sets","author":"A. Ambainis","year":"1996","unstructured":"A. Ambainis, R. Freivalds, and C. Smith. General inductive inference types based on linearly ordered sets. In C. Puech and R. Reischuk, editors, Proceedings of the 13th Symposium on the Theoretical Aspects of Computer Science, volume LNCS1046, pages 243\u2013253. Springer, 1996."},{"key":"35_CR2","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"D. Angluin and C. H. Smith. Inductive inference: Theory and methods. Computing Surveys, 15:237\u2013269, 1983.","journal-title":"Computing Surveys"},{"key":"35_CR3","doi-asserted-by":"crossref","unstructured":"K. Ambos-Spies. Resource-bounded genericity. In Proceedings of the 10th Conference on Structure in Complexity Theory, pages 162\u2013181. IEEE Computer Society, 1995.","DOI":"10.1109\/SCT.1995.514855"},{"key":"35_CR4","series-title":"Lect Notes Comput Sci","first-page":"63","volume-title":"Resourcebounded genericity, stochasticity and weak randomness","author":"K. Ambos-Spies","year":"1996","unstructured":"K. Ambos-Spies, E. Mayordomo, Y. Wang, and X. Zheng. Resourcebounded genericity, stochasticity and weak randomness. In C. Puech and R. Reischuk, editors, Proceedings of the 13th Symposium on the Theoretical Aspects of Computer Science, volume LNCS 1046, pages 63\u201374. Springer, 1996."},{"key":"35_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/S0019-9958(75)90261-2","volume":"28","author":"L. Blum","year":"1975","unstructured":"L. Blum and M. Blum. Toward a mathematical theory of inductive inference. Information and Control, 28:125\u2013155, 1975.","journal-title":"Information and Control"},{"key":"35_CR6","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/3-540-60922-9_18","volume-title":"STACS 96","author":"J\u0101nis B\u0101rzdi\u0146s","year":"1996","unstructured":"J. B\u0101rzdi\u0146\u0161, R. Freivalds, and C. Smith. Learning with confidence. In Proceedings of STACS\u201996, 1996."},{"key":"35_CR7","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1137\/0210008","volume":"10","author":"C.G. Bennet","year":"1981","unstructured":"C.G. Bennet and J. Gill. Relative to a random oracle A, P a \u2260 NP a \u2260 co-NP a with probability 1. SIAM Journal of Computer Science, 10:96\u2013113, 1981.","journal-title":"SIAM Journal of Computer Science"},{"key":"35_CR8","doi-asserted-by":"crossref","unstructured":"M. Blum and R. Impagliazzo. Generic oracles and oracle classes. In Proceedings of the 28th Symposium on the Foundations of Computer Science, pages 118\u2013126. IEEE Computer Soceity, 1987.","DOI":"10.1109\/SFCS.1987.30"},{"key":"35_CR9","series-title":"Lect Notes Comput Sci","first-page":"13","volume-title":"Compressibility and resource bounded measure","author":"H. Buhrman","year":"1996","unstructured":"H. Buhrman and L. Longpr\u00e9. Compressibility and resource bounded measure. In C. Puech and R. Reischuk, editors, Proceedings of the 13th Symposium on the Theoretical Aspects of Computer Science, volume LNCS1046, pages 13\u201324. Springer, 1996."},{"key":"35_CR10","doi-asserted-by":"crossref","unstructured":"J. Balc\u00e1zar and E. Mayordomo. A note on genericity and bi-immunity. In Proceedings of the 10th Conference on Structure in Complexity Theory, pages 193\u2013196. IEEE Computer Society, 1995.","DOI":"10.1109\/SCT.1995.514857"},{"key":"35_CR11","doi-asserted-by":"crossref","unstructured":"H. Buhrman and E. Mayordomo. An excursion to the Kolmogorov random strings. In Proceedings of the 10th Conference on Structure in Complexity Theory, pages 197\u2013205. IEEE Computer Society, 1995.","DOI":"10.1109\/SCT.1995.514858"},{"key":"35_CR12","volume-title":"Le\u00e7ons sur les fonctions de variables r\u00e9eles","author":"E. Borel","year":"1905","unstructured":"E. Borel. Le\u00e7ons sur les fonctions de variables r\u00e9eles. Gauthier-Villars, Paris, 1905."},{"key":"35_CR13","volume-title":"Le\u00e7ons sur la th\u00e9orie des fonctions","author":"E. Borel","year":"1914","unstructured":"E. Borel. Le\u00e7ons sur la th\u00e9orie des fonctions. Gauthier-Villars, Paris, 1914."},{"issue":"1","key":"35_CR14","doi-asserted-by":"publisher","first-page":"24","DOI":"10.1016\/S0022-0000(05)80084-4","volume":"49","author":"R. Chang","year":"1994","unstructured":"Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan H\u2222stad, Desh Ranjan, and Pankaj Rohatgi. The random oracle hypothesis is false. Journal of Computer and System Sciences, 49(1):24\u201339, August 1994.","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"35_CR15","doi-asserted-by":"publisher","first-page":"643","DOI":"10.2307\/1969101","volume":"44","author":"P. Erd\u00f6s","year":"1943","unstructured":"P. Erd\u00f6s. Some remarks on set theory. Ann. Math, 44(2):643\u2013646, 1943.","journal-title":"Ann. Math"},{"key":"35_CR16","doi-asserted-by":"crossref","unstructured":"S. Fenner. Notions of resource-bounded category and genericity. In Proceedings of the 6th Conference on Structure in Complexity Theory, pages 196\u2013212. IEEE Computer Soceity, 1991.","DOI":"10.1109\/SCT.1991.160262"},{"key":"35_CR17","doi-asserted-by":"crossref","unstructured":"S. Fenner. Resource-bounded Baire category: A stronger approach. In Proceedings of the 10th Conference on Structure in Complexity Theory, pages 182\u2013192. IEEE Computer Society, 1995.","DOI":"10.1109\/SCT.1995.514856"},{"issue":"1","key":"35_CR18","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1016\/S0304-3975(97)00175-8","volume":"197","author":"L. Fortnow","year":"1998","unstructured":"L. Fortnow, R. Freivalds, W. Gasarch, M. Kummer, S. Kurtz, C. Smith, and F. Stephan. On the relative sizes of learnable sets. Theoretical Computer Science, 197(1\u20132):139\u2013156, 1998.","journal-title":"Theoretical Computer Science"},{"key":"35_CR19","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"558","DOI":"10.1007\/3-540-60084-1_105","volume-title":"Measure, category and learning theory","author":"L. Fortnow","year":"1995","unstructured":"L. Fortnow, R. Freivalds, W. Gasarch, M. Kummer, S. Kurtz, C. Smith, and F. Stephan. Measure, category and learning theory. In Proceedings of ICALP\u201995, LNCS Vol. 944, pages 558\u2013569, 1995."},{"issue":"2","key":"35_CR20","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1016\/0020-0190(93)90216-V","volume":"45","author":"J. Foster","year":"1993","unstructured":"J. Foster. The generic oracle hypothesis is false. Information Processing Letters, 45(2):59\u201362, 1993.","journal-title":"Information Processing Letters"},{"key":"35_CR21","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1007\/BFb0019357","volume-title":"Baltic Computer Science","author":"R. Freivalds","year":"1991","unstructured":"R. Freivalds. Inductive inference of recursive functions: Qualitative theory. In J. B\u0101rzdin\u0161 and D. Bj\u00f8rner, editors, Baltic Computer Science, pages 77\u2013110. Springer Verlag, 1991.Lecture Notes in Computer Science, Vol. 502."},{"key":"35_CR22","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1006\/inco.1993.1068","volume":"107","author":"R. Freivalds","year":"1993","unstructured":"R. Freivalds and C. Smith. On the power of procrastination for machine learning. Information and Computation, 107:237\u2013271, 1993.","journal-title":"Information and Computation"},{"key":"35_CR23","doi-asserted-by":"publisher","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E. M. Gold","year":"1967","unstructured":"E. M. Gold. Language identi.cation in the limit. Information and Control, 10:447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"35_CR24","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/3-540-60922-9_3","volume-title":"On the complexity of random strings","author":"M. Kummer","year":"1996","unstructured":"M. Kummer. On the complexity of random strings. In C. Puech and R. Reischuk, editors, Proceedings of the 13th Symposium on the Theoretical Aspects of Computer Science, volume LNCS 1046, pages 25\u201338. Springer, 1996."},{"key":"35_CR25","unstructured":"C. Kuratowski. Topologie, 4th edition, volume 20\u201321 of Monografie Matematyczne. Panstwowe Wydawnictwo Naukowe, 1958."},{"issue":"1","key":"35_CR26","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/S0019-9958(83)80023-0","volume":"57","author":"S. A. Kurtz","year":"1983","unstructured":"Stuart A. Kurtz. On the random oracle hypothesis. Information and Control, 57(1):40\u201347, 1983.","journal-title":"Information and Control"},{"issue":"4","key":"35_CR27","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"Carsten Lund","year":"1992","unstructured":"C. Lund, L. Fortnow, H. Karlo., and N. Nisan. Algebraic methods for interactive proof systems. Journal of the ACM, 39(4), 1992.","journal-title":"Journal of the ACM"},{"key":"35_CR28","first-page":"201","volume":"38","author":"L. Lisagor","year":"1981","unstructured":"L. Lisagor. The Banach-Mazur game. Translated Version of Matematicheskij Sbornik, 38:201\u2013206, 1981.","journal-title":"Translated Version of Matematicheskij Sbornik"},{"key":"35_CR29","doi-asserted-by":"publisher","first-page":"1100","DOI":"10.1137\/0219076","volume":"19","author":"J. Lutz","year":"1990","unstructured":"J. Lutz. Category and measure in complexity classes. SIAM Journal of Computing, 19:1100\u20131131, 1990.","journal-title":"SIAM Journal of Computing"},{"key":"35_CR30","doi-asserted-by":"crossref","unstructured":"J. Lutz. The quantitative structure of exponential time. In Proceedings of the 8th Structure in Complexity Theory Conference, pages 158\u2013175. IEEE Computer Society, 1993.","DOI":"10.1109\/SCT.1993.336530"},{"key":"35_CR31","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/3-540-60922-9_8","volume-title":"Observations on measures and lowness for \u0394P 2","author":"J. Lutz","year":"1996","unstructured":"J. Lutz. Observations on measures and lowness for \u0394P 2. In C. Puech and R. Reischuk, editors, Proceedings of the 13th Symposium on the Theoretical Aspects of Computer Science, volume LNCS 1046, pages 87\u201398. Springer, 1996."},{"key":"35_CR32","doi-asserted-by":"crossref","unstructured":"K. Mehlhorn. On the size of sets of computable functions. In Proceedings of the 14th Symposium on Switching and Automata Theory, pages 190\u2013196. IEEE Computer Soceity, 1973.","DOI":"10.1109\/SWAT.1973.23"},{"key":"35_CR33","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1016\/0304-3975(76)90087-6","volume":"2","author":"E. Minicozzi","year":"1976","unstructured":"E. Minicozzi. Some natural properties of strong-identification in inductive inference. Theoretical Computer Science, 2:345\u2013360, 1976.","journal-title":"Theoretical Computer Science"},{"key":"35_CR34","unstructured":"M. Machtey and P. Young. An Introduction to the General Theory of Algorithms. North-Holland, New York, 1978."},{"key":"35_CR35","doi-asserted-by":"crossref","unstructured":"D. Osherson, M. Stob, and S. Weinstein. Systems that Learn. MIT Press, Cambridge, Mass., 1986.","DOI":"10.7551\/mitpress\/6609.001.0001"},{"key":"35_CR36","doi-asserted-by":"crossref","unstructured":"J. Oxtoby. Measure and Category. Springer-Verlag, 1971.","DOI":"10.1007\/978-1-4615-9964-7"},{"issue":"2","key":"35_CR37","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1145\/62044.62053","volume":"36","author":"L. Pitt","year":"1989","unstructured":"L. Pitt. Probabilistic inductive inference. Journal of the ACM, 36(2):383\u2013433, 1989.","journal-title":"Journal of the ACM"},{"key":"35_CR38","unstructured":"H. Putnam. Probability and confirmation. In Mathematics, Matter and Method, volume 1. Cambridge University Press, 1975."},{"key":"35_CR39","unstructured":"W. Sierpinski. Hypoth`ese du continu, volume 4. Monografie Matematyczne, 1934."},{"key":"35_CR40","doi-asserted-by":"publisher","first-page":"276","DOI":"10.4064\/fm-22-1-276-280","volume":"28","author":"W. Sierpinski","year":"1934","unstructured":"W. Sierpinski. Sur la dualit\u00e9 entre la premi\u00e8re cat\u00e9gore et la mesure nulle. Fund. Math., 28:276\u2013280, 1934.","journal-title":"Fund. Math."},{"issue":"4","key":"35_CR41","doi-asserted-by":"publisher","first-page":"1144","DOI":"10.1145\/322344.322356","volume":"29","author":"C. H. Smith","year":"1982","unstructured":"C. H. Smith. The power of pluralism for automatic program synthesis. Journal of the ACM, 29(4):1144\u20131165, 1982.","journal-title":"Journal of the ACM"},{"key":"35_CR42","doi-asserted-by":"crossref","unstructured":"C. Smith. A Recursive Introduction to the Theory of Computation. Springer-Verlag, 1994.","DOI":"10.1007\/978-1-4419-8501-9"},{"key":"35_CR43","doi-asserted-by":"crossref","unstructured":"C. Smith. Three decades of team learning. In Proceedings of AII\/ALT\u201994, Lecture Notes in Artificial Intelligence. Springer Verlag, 1994.","DOI":"10.1007\/3-540-58520-6_66"}],"container-title":["Lecture Notes in Computer Science","LATIN 2002: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45995-2_35","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,22]],"date-time":"2020-04-22T09:09:16Z","timestamp":1587546556000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45995-2_35"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540434009","9783540459958"],"references-count":43,"URL":"https:\/\/doi.org\/10.1007\/3-540-45995-2_35","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2002]]}}}