{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T09:45:23Z","timestamp":1777455923935,"version":"3.51.4"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1990,6,1]],"date-time":"1990-06-01T00:00:00Z","timestamp":644198400000},"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":[[1990,6]]},"DOI":"10.1007\/bf00116036","type":"journal-article","created":{"date-parts":[[2004,11,1]],"date-time":"2004-11-01T01:33:03Z","timestamp":1099272783000},"page":"165-196","source":"Crossref","is-referenced-by-count":16,"title":["Learning nested differences of intersection-closed concept classes"],"prefix":"10.1007","volume":"5","author":[{"given":"David","family":"Helmbold","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Sloan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Manfred K.","family":"Warmuth","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A. Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., and Warmuth, M.K. (1989). Learnability and the Vapnik-Chervonenkis dimension.Journal of the ACM,36, 929?965.","journal-title":"Journal of the ACM"},{"key":"CR2","doi-asserted-by":"crossref","unstructured":"Board, R. and Pitt, L. (1990). On the necessity of Occam algorithms.Proceedings of the Twenty-Secnd Annual ACM Symposium on Theory of Computing.","DOI":"10.1145\/100216.100223"},{"key":"CR3","unstructured":"Boucheron, S. (1988). Learnability from positive examples in the Valiant framework. Unpublished manuscript."},{"key":"CR4","volume-title":"Lecture Notes in Mathematics No. 1097","author":"R.M. Dudley","year":"1984","unstructured":"Dudley, R.M. (1984). A course on empirical processes.Lecture Notes in Mathematics No. 1097. New York: Springer-Verlag."},{"key":"CR5","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","volume":"82","author":"A. Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M., and Valiant, L. (1989). A general lower bound on the number examples needed for learning.Information and Computation,82, 247?261.","journal-title":"Information and Computation"},{"key":"CR6","first-page":"7","volume":"4","author":"D. Haussler","year":"1989","unstructured":"Haussler, D. (1989). Learning conjunctive concepts in structural domains.Machine Learning,4, 7?40.","journal-title":"Machine Learning"},{"key":"CR7","unstructured":"Haussler, D., Kearns, M., Littlestone, N., and Warmuth, M.K. (1990). Equivalence of models for polynomial learnability.Information and Computation. To appear."},{"key":"CR8","doi-asserted-by":"crossref","unstructured":"Haussler, D., Littlestone, N., and Warmuth, M.K. (1988). Predicting {0, 1}-functions on randomly drawn points.Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pp. 100?109. White Plains, NY: IEEE. Tech. Report, U.C. Santa Cruz. To appear (longer version).","DOI":"10.1109\/SFCS.1988.21928"},{"key":"CR9","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D. and Welzl, E. (1987). Epsilon-nets and simplex range queries.Discrete Computational Geometry,2, 127?151.","journal-title":"Discrete Computational Geometry"},{"key":"CR10","series-title":"Technical Report UCSC-CRL-89-23","volume-title":"Learning lattices and reversible, commutative regular languages","author":"D. Helmbold","year":"1989","unstructured":"Helmbold, D., Sloan, R., and Warmuth, M.K. (1989a).Learning lattices and reversible, commutative regular languages. (Technical Report UCSC-CRL-89?23). Santa Cruz, CA: U.C. Santa Cruz, Computer Research Laboratory."},{"key":"CR11","series-title":"Technical Report UCSC-CRL-89-19","volume-title":"Learning nested differences of intersection-closed concept classes","author":"D. Helmbold","year":"1989","unstructured":"Helmbold, D., Sloan, R., and Warmuth, M.K. (1989b).Learning nested differences of intersection-closed concept classes. (Technical Report UCSC-CRL-89?19) Santa Cruz, CA: U.C. Santa Cruz, Computer Research Laboratory."},{"key":"CR12","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/B978-0-08-094829-4.50006-4","volume-title":"Proceedings of the Second Workshop on Computational Learning Theory","author":"D. Helmbold","year":"1989","unstructured":"Helmbold, D., Sloan, R., and Warmuth, M.K. (1989c). Learning nested differences of intersection-closed concept classes.Proceedings of the Second Workshop on Computational Learning Theory (pp. 41?56). Santa Cruz, CA: Morgan Kaufmann."},{"key":"CR13","doi-asserted-by":"crossref","unstructured":"Kearns, M., Li, M., Pitt, L., and Valiant, L. (1987). On the learnability of boolean formulae.Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 285?295). New York.","DOI":"10.1145\/28395.28426"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"Kearns, M. and Valiant, L.G. (1989). Cryptographic limitations on learning boolean formulae and finite automata.Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing (pp. 433?444). Seattle, Washington.","DOI":"10.1145\/73007.73049"},{"key":"CR15","first-page":"285","volume":"2","author":"N. Littlestone","year":"1988","unstructured":"Littlestone, N. (1988). Learning when irrelevant attributes abound: A new linear-threshold algorithm.Machine Learning,2, 285?318.","journal-title":"Machine Learning"},{"key":"CR16","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1016\/B978-0-08-094829-4.50022-2","volume-title":"Proceedings of the Second Workshop on Computational Learning Theory","author":"N. Littlestone","year":"1989","unstructured":"Littlestone, N. (1989). From on-line to batch learning.Proceedings of the Second Workshop on Computational Learning Theory (pp. 269?284). Santa Cruz, CA: Morgan Kaufmann."},{"key":"CR17","series-title":"Technical Report UCSC-CRL-89-19","first-page":"256","volume-title":"The weighted majority algorithm","author":"N. Littlestone","year":"1989","unstructured":"Littlestone, N. and Warmuth, M.K. (1989).The weighted majority algorithm (Technical Report UCSC-CRL-89?19). Santa Cruz, CA: U.C. Santa Cruz, Computer Research Laboratory. An extended abstract is available inProceedings of the 30th Annual Symposium on Foundations of Computer Science (pp. 256?261). Research Triangle, NC: October 1989."},{"key":"CR18","doi-asserted-by":"crossref","unstructured":"Natarajan, B.K. (1987). On learning boolean functions.Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (pp. 296-304). New York.","DOI":"10.1145\/28395.28427"},{"key":"CR19","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1080\/03081077808960690","volume":"4","author":"J. Pearl","year":"1978","unstructured":"Pearl, J. (1978). On the connection between the complexity and credibility of inferred models.Journal of General Systems,4, 255?264.","journal-title":"Journal of General Systems"},{"key":"CR20","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L. and Valiant, L.G. (1988). Computational limitations on learning from examples.Journal of the ACM,35, 965?984.","journal-title":"Journal of the ACM"},{"key":"CR21","doi-asserted-by":"crossref","unstructured":"Pitt, L. and Warmuth, M.K. (1990a). The minimum consistent DFA problem cannot be approximated within any polynomial.Journal of the ACM. To appear.","DOI":"10.1145\/73007.73048"},{"key":"CR22","doi-asserted-by":"crossref","unstructured":"Pitt, L. and Warmuth, M.K. (1990b). Prediction preserving reducibility.Journal of Computer and System Sciences. To appear in special issue consisting of papers from the third annual IEEE Conference on Structures in Complexity Theory, 1988.","DOI":"10.1016\/0022-0000(90)90028-J"},{"key":"CR23","first-page":"229","volume":"2","author":"R.L. Rivest","year":"1987","unstructured":"Rivest, R.L. (1987). Learning decision lists.Machine Learning,2, 229?246.","journal-title":"Machine Learning"},{"key":"CR24","series-title":"Technical Report TR-10-88","volume-title":"Examplar-based learning: theory and implementation","author":"S. Salzberg","year":"1988","unstructured":"Salzberg, S. (1988).Examplar-based learning: theory and implementation. (Technical Report TR-10?88) Cambridge, MA: Harvard University, Center for Research in Computing Technology."},{"key":"CR25","unstructured":"Shvaytser, H. (1988). Linear manifolds are learnable from positive examples. Unpublished manuscript."},{"key":"CR26","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"Valiant, L.G. (1984). A theory of the learnable.Communications of the ACM,27, 1134?1142.","journal-title":"Communications of the ACM"},{"key":"CR27","volume-title":"Estimation of Dependences Based on Empirical Data","author":"V.N. Vapnik","year":"1982","unstructured":"Vapnik, V.N. (1982).Estimation of Dependences Based on Empirical Data. New York: Springer-Verlag."},{"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. and Chervonenkis, A.Y. (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\/BF00116036.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF00116036\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF00116036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,3]],"date-time":"2020-04-03T17:11:10Z","timestamp":1585933870000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF00116036"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,6]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1990,6]]}},"alternative-id":["BF00116036"],"URL":"https:\/\/doi.org\/10.1007\/bf00116036","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,6]]}}}