{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T16:17:36Z","timestamp":1778689056123,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1989,10,1]],"date-time":"1989-10-01T00:00:00Z","timestamp":623203200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[1989,10]]},"DOI":"10.1007\/bf00114804","type":"journal-article","created":{"date-parts":[[2004,10,31]],"date-time":"2004-10-31T18:47:23Z","timestamp":1099248443000},"page":"67-97","source":"Crossref","is-referenced-by-count":66,"title":["On learning sets and functions"],"prefix":"10.1007","volume":"4","author":[{"given":"B. K.","family":"Natarajan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1145\/356914.356918","volume":"15","author":"D. Angluin","year":"1983","unstructured":"Angluin, D. & Smith, C. H. (1983). Inductive inference: Theory and methods. Computing Surveys, 15, 237?269.","journal-title":"Computing Surveys"},{"key":"CR2","series-title":"Technical Report YALEU\/ DCS-464)","volume-title":"Learning regular sets from queries and counter-examples","author":"D. Angluin","year":"1986","unstructured":"Angluin, D. (1986). Learning regular sets from queries and counter-examples (Technical Report YALEU\/ DCS-464). New Haven, CT: Yale University, Department of Computer Science."},{"key":"CR3","first-page":"343","volume":"2","author":"D. Angluin","year":"1968","unstructured":"Angluin, D. & Laird, P. (1968). Learning from noisy examples. Machine Learning, 2, 343?370.","journal-title":"Machine Learning"},{"key":"CR4","first-page":"80","volume-title":"Proceedings of the Workshop on Computational Learning Theory","author":"G. M. Benedeck","year":"1988","unstructured":"Benedeck, G. M., & Itai, N. (1988). Learning by fixed distributions Proceedings of the Workshop on Computational Learning Theory (pp. 80?90). Cambridge, MA: Morgan Kaufmann."},{"key":"CR5","first-page":"61","volume-title":"Proceedings of the Symposium on Foundations of Computer Science","author":"P. Berman","year":"1987","unstructured":"Berman, P., & Roos, R. (1987). Learning one-counter languages in polynomial time. Proceedings of the Symposium on Foundations of Computer Science (pp. 61?67). Los Angeles, CA: IEEE Computer Society Press."},{"key":"CR6","first-page":"9","volume-title":"Proceedings of the Workshop on Computational Learning Theory","author":"A. Blum","year":"1988","unstructured":"Blum, A., & Rivest, R. (1988). Training a 3-node neural network is NP-complete. Proceedings of the Workshop on Computational Learning Theory (pp. 9?18). Cambridge, MA: Morgan Kaufmann."},{"key":"CR7","first-page":"273","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"A. Blumer","year":"1986","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. (1986). Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension. Proceedings of the ACM Symposium on Theory of Computing (pp. 273?282). Berkeley, CA: ACM Press."},{"key":"CR8","doi-asserted-by":"crossref","first-page":"675","DOI":"10.1137\/0206049","volume":"6","author":"J. Gill","year":"1977","unstructured":"Gill, J. (1977). Computational complexity of probabilistic turing machines. SIAM Journal of Computing, 6, 675?695.","journal-title":"SIAM Journal of Computing"},{"key":"CR9","first-page":"280","volume-title":"Proceedings of the Workshop on Computational Learning Theory","author":"D. Haussler","year":"1988","unstructured":"Haussler, D., Littlestone, N., & Warmuth, M. (1988). Predicting {0.1} functions on randomly drawn points. Proceedings of the Workshop on Computational Learning Theory (pp. 280?296). Cambridge, MA: Morgan Kaufmann."},{"key":"CR10","first-page":"285","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"M. Kearns","year":"1987","unstructured":"Kearns, M., Li, M., Pitt, L., & Valiant, L. G. (1987a). On the learnability of Boolean formulae. Proceedings of the ACM Symposium on Theory of Computing (pp. 285?295). New York, NY: ACM Press."},{"key":"CR11","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1016\/B978-0-934613-41-5.50037-4","volume-title":"Proceedings of the Fourth International Workshop on Machine Learning","author":"M. Kearns","year":"1987","unstructured":"Kearns, M., Li, M., Pitt, L. & Valiant, L. G. (1987b). Recent results on Boolean concept learning. Proceedings of the Fourth International Workshop on Machine Learning (pp. 337?352). Irvine, CA: Morgan Kaufmann."},{"key":"CR12","unstructured":"Laird, P. (1987). Learning from data good and bad. Doctoral Dissertation, Department of Computer Science, Yale University, New Haven, CT."},{"key":"CR13","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N. (1988). Learning quickly when irrelevant attributes abound. Machine Learning, 2, 285?318.","journal-title":"Machine Learning"},{"key":"CR14","first-page":"47","volume":"1","author":"T. M. Mitchell","year":"1986","unstructured":"Mitchell, T. M., Keller, R. M., & Kedar-Cabelli, S. T. (1986). Explanation based generalization: A unifying view. Machine Learning, 1, 47?80.","journal-title":"Machine Learning"},{"key":"CR15","series-title":"Technical Report CMU-RI-TR-86-17","first-page":"296","volume-title":"On learning Boolean functions","author":"B. K. Natarajan","year":"1986","unstructured":"Natarajan, B. K. (1986). On learning Boolean functions (Technical Report CMU-RI-TR-86?17). Pittsburgh, PA: Carnegie Mellon University, Robotics Institute. Also Proceedings of the ACM Symposium on Theory of Computing, 1987 (pp. 296?304). New York, NY: ACM Press."},{"key":"CR16","series-title":"Technical Report CMU-RI-TR87-25","volume-title":"Two new frameworks for learning","author":"B. K. Natarajan","year":"1987","unstructured":"Natarajan, B. K. (1987). Two new frameworks for learning (Technical Report CMU-RI-TR87?25). Pittsburgh, PA: Carnegie Mellon University, Robotics Institute."},{"key":"CR17","volume-title":"Proceedings of the Workshop on Computational Learning Theory","author":"B. K. Natarajan","year":"1988","unstructured":"Natarajan, B. K. (1988a). Learning over classes of distributions. Proceedings of the Workshop on Computational Learning Theory. Cambridge, MA: Morgan Kaufmann."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Natarajan, B. K. (1988b). Some results on learning. Unpublished manuscript.","DOI":"10.21236\/ADA210591"},{"key":"CR19","series-title":"Technical Report CMU-RI-TR4-89","doi-asserted-by":"crossref","DOI":"10.21236\/ADA210593","volume-title":"On learning from exercises","author":"B. K. Natarajan","year":"1989","unstructured":"Natarajan, B. K. (1989a). On learning from exercises (Technical Report CMU-RI-TR4?89). Pittsburgh, PA: Carnegie Mellon University, Robotics Institute."},{"key":"CR20","unstructured":"Natarajan, B. K., Probably approximate learning over classes of distributions (Technical Report HPL-SAL-89-29). Palo Alto, CA: Hewlett Packard Research Laboratories."},{"key":"CR21","first-page":"402","volume-title":"Proceedings of the Fifth International Symposium on Machine Learning","author":"B. K. Natarajan","year":"1988","unstructured":"Natarajan, B. K. & Tadepalli, P. (1988). Two new frameworks for learning. Proceedings of the Fifth International Symposium on Machine Learning (pp. 402?415). Ann Arbor, MI: Morgan Kaufmann."},{"key":"CR22","first-page":"60","volume-title":"Proceedings of 3rd IEEE Conference on Structure in Complexity Theory","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., & Warmuth, M. (1988). Reductions among prediction problems: On the difficulty of predicting automata. Proceedings of 3rd IEEE Conference on Structure in Complexity Theory (pp. 60?69). Washington, D. C.: ACM Press."},{"key":"CR23","volume-title":"Convergence of stochastic processes","author":"J. Pollard","year":"1986","unstructured":"Pollard, J. (1986). Convergence of stochastic processes. New York: Springer-Verlag."},{"key":"CR24","first-page":"229","volume":"2","author":"R. Rivest","year":"1987","unstructured":"Rivest, R. (1987). Learning decision lists. Machine Learning, 2, 229?246.","journal-title":"Machine Learning"},{"key":"CR25","first-page":"78","volume-title":"Proceedings of the Symposium on Foundations of Computer Science","author":"R. Rivest","year":"1987","unstructured":"Rivest, R., & Schapire, R. E. (1987). Diversity based inference of finite automata. Proceedings of the Symposium on Foundations of Computer Science (pp. 78?87). Los Angeles, CA: IEEE Computer Society Press."},{"key":"CR26","volume-title":"Parallel distributed processing","year":"1986","unstructured":"Rumelhart, D., & McClelland, J. (Eds.). (1986). Parallel distributed processing. Cambridge, MA: MIT Press."},{"key":"CR27","first-page":"436","volume-title":"Proceedings of the ACM Symposium on Theory of Computing","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Proceedings of the ACM Symposium on Theory of Computing (pp. 436?445). Washington, D.C.: ACM Press."},{"key":"CR28","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"Vapnik, V. N. & Chervonenkis, A. Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of probability and its applications, 16, 264?280.","journal-title":"Theory of probability and its applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00114804.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00114804\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00114804","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T17:07:29Z","timestamp":1585933649000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00114804"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["BF00114804"],"URL":"https:\/\/doi.org\/10.1007\/bf00114804","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]}}}