{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,22]],"date-time":"2025-12-22T22:12:20Z","timestamp":1766441540942},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"3-4","license":[{"start":{"date-parts":[[1995,12,1]],"date-time":"1995-12-01T00:00:00Z","timestamp":817776000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["NGCO"],"published-print":{"date-parts":[[1995,12]]},"DOI":"10.1007\/bf03037231","type":"journal-article","created":{"date-parts":[[2009,4,22]],"date-time":"2009-04-22T03:02:11Z","timestamp":1240369331000},"page":"369-409","source":"Crossref","is-referenced-by-count":34,"title":["Polynomial learnability and Inductive Logic Programming: Methods and results"],"prefix":"10.1007","volume":"13","author":[{"given":"William W.","family":"Cohen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"C. David","family":"Page","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF03037231_CR1","unstructured":"Aizenstein, H., \u201cOn the Learnability of Disjunctive Normal Form Formulas and Decision Trees,\u201dPh. D. thesis, University of Illinois at Urbana-Champaign, 1992."},{"key":"BF03037231_CR2","first-page":"147","volume":"9","author":"D. Angluin","year":"1992","unstructured":"Angluin, D., Frazier, M. and Pitt, L., \u201cLearning Conjunctions of Horn Clauses,\u201dMachine Learning, 9, pp. 147\u2013164, 1992.","journal-title":"Machine Learning"},{"key":"BF03037231_CR3","first-page":"4","volume":"2","author":"D. Angluin","year":"1988","unstructured":"Angluin, D., \u201cQueries and Concept Learning,\u201dMachine Learning, 2 4, 1988.","journal-title":"Machine Learning"},{"key":"BF03037231_CR4","doi-asserted-by":"crossref","unstructured":"Angluin, D., \u201cEquivalence Queries and Approximate Fingerprints\u201d InProceedings of the 1989 Workshop on Computational Learning Theory, Santa Cruz, California 1989.","DOI":"10.1016\/B978-0-08-094829-4.50012-X"},{"key":"BF03037231_CR5","doi-asserted-by":"crossref","unstructured":"Arimura, H., Ishizaka, H., and Shinohara, T., \u201cPolynomial Time Inference of a Subclass of Context-Free Transformations,\u201d inProceedings of the Fifth Workshop on Computational Learning Theory (COLT-92), The Association for Computing Machinery, New York, pp. 136\u2013143 1992.","DOI":"10.1145\/130385.130400"},{"issue":"4","key":"BF03037231_CR6","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., \u201cClassifiying Learnable Concepts with the Vapnik-Chervonenkis Dimension,\u201dJournal of the Association for Computing Machinery, 36, 4, pp. 929\u2013965, 1989.","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"2","key":"BF03037231_CR7","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1016\/0004-3702(88)90001-X","volume":"36","author":"W. Buntine","year":"1988","unstructured":"Buntine, W., \u201cGeneralized Subsumption and Its Application to Induction and Redundancy,\u201dArtificial Intelligence, 36, 2, pp. 149\u2013176, 1988.","journal-title":"Artificial Intelligence"},{"key":"BF03037231_CR8","volume-title":"A Theory of Learning Classification Rules","author":"W. Buntine","year":"1990","unstructured":"Buntine, W., \u201cA Theory of Learning Classification Rules,\u201dPh.D thesis, School of Computing Science, University of Technology, Sydney, 1990."},{"key":"BF03037231_CR9","unstructured":"Cohen, W. W., \u201cCryptographic Limitations on Learning One-Clause Logic Programs,\u201d inProceedings of the Tenth National Conference on Artificial Intelligence, Washington, D. C., 1993."},{"key":"BF03037231_CR10","unstructured":"Cohen, W. W., \u201cLearnability of Restricted Logic Programs,\u201d inProceedings of the Third International Workshop on Inductive Logic Programming, Bled, Slovenia, 1993."},{"key":"BF03037231_CR11","unstructured":"Cohen, W. W., \u201cA Pac-Learning Algorithm for a Restricted Class of Recursive Logic Programs,\u201d inProceedings of the Tenth National Conference on Artificial Intelligence, Washington, D.C., 1993."},{"key":"BF03037231_CR12","unstructured":"Cohen, W. W., \u201cPac-Learning Non-Recursive Prolog Clauses,\u201d to appearArtificial Intelligence, 1993."},{"key":"BF03037231_CR13","doi-asserted-by":"crossref","unstructured":"Cohen, W. W., \u201cThe Pac-Learnability of Recursive Logic Programs,\u201d in preparation, 1994.","DOI":"10.1613\/jair.1917"},{"key":"BF03037231_CR14","unstructured":"Cohen, W. W., \u201cPac-Learning Nondeterminate Clauses\u201d inProceedings of the Eleventh National Conference on Artificial Intelligence, Seattle, WA, 1994."},{"key":"BF03037231_CR15","unstructured":"Cohen, W. W., \u201cRecovering Software Specifications with Inductive Logic Programming,\u201d inProceedings of the Eleventh National Conference on Artificial Intelligence, Seattle, WA, 1994."},{"key":"BF03037231_CR16","doi-asserted-by":"crossref","unstructured":"DeRaedt, L. and D\u017eeroski, S., \u201cjk-Clausal Theories Are PAC-Learnable,\u201dArtificial Intelligence, to appear, 1994.","DOI":"10.1016\/0004-3702(94)90112-0"},{"key":"BF03037231_CR17","doi-asserted-by":"crossref","unstructured":"D\u017eeroski, S., Muggleton, S., and Russell, S., \u201cPac-Learnability of Determinate Logic Programs,\u201d inProceedings of the 1992 Workshop on Computational Learning Theory, Pittsburgh, Pennsylvania, 1992.","DOI":"10.1145\/130385.130399"},{"key":"BF03037231_CR18","unstructured":"Frazier, M. and Page, C. D., \u201cLearnability in Inductive Logic Programming: Some Basic Results and Techniques,\u201d inProceedings of the 11th National Conference on Artificial Intelligence (AAAI-93), Menlo Park, CA, AAAI Press, 1993."},{"key":"BF03037231_CR19","unstructured":"Frazier, M. and Page, C. D., \u201cLearnability of Recursive, Non-determinate Theories: Some Basic Results and Techniques,\u201d inProceedings of the Third International Workshop on Inductive Logic Programming, Ljubljana, Slovenia, pp. 103\u2013126, 1993.J. Stefan Institute Technical Report, IJS-DP-6707."},{"key":"BF03037231_CR20","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1016\/0020-0190(94)00074-3","volume":"51","author":"M. Frazier","year":"1994","unstructured":"Frazier, M. and Page, C. D., \u201cPrefix Grammars: An Alternative Characterization of the Regular Languages,\u201dInformation Processing Letters, 51, pp. 67\u201371, 1994.","journal-title":"Information Processing Letters"},{"key":"BF03037231_CR21","unstructured":"Frazier, M., \u201cMatters Horn and Other Features in the Computational Learning Theory Landscape: The Notion of Membership,\u201dPh.D thesis, University of Illinois at Urbana-Champaign, 1994."},{"key":"BF03037231_CR22","first-page":"61","volume-title":"Proceedings of the Fourth Annual Workshop on Computational Learning Theory","author":"D. Haussler","year":"1991","unstructured":"Haussler, D., Kearns, M., and Schapire, R., \u201cBounds on the Sample Complexity of Bayesian Learning Using Information Theory and VC Dimension,\u201d inProceedings of the Fourth Annual Workshop on Computational Learning Theory, San Mateo, CA, Morgan Kaufmann, pp. 61\u201374, 1991."},{"issue":"1","key":"BF03037231_CR23","first-page":"83","volume":"14","author":"D. Haussler","year":"1994","unstructured":"Haussler, D., Kearns, M., and Schapire, R., \u201cBounds on the Sample Complexity of Bayesian Learning Using Information Theory and VC Dimension,\u201dMachine Learning, 14, 1, pp. 83\u2013113, January 1994.","journal-title":"Machine Learning"},{"key":"BF03037231_CR24","first-page":"1","volume":"4","author":"D. Haussler","year":"1989","unstructured":"Haussler, D., \u201cLearning Conjunctive Concepts in Structural Domains,\u201dMachine Learning, 4, 1, 1989.","journal-title":"Machine Learning"},{"key":"BF03037231_CR25","doi-asserted-by":"crossref","first-page":"399","DOI":"10.1145\/130385.130428","volume-title":"Proc. 5th Annu. Workshop on Comput. Learning Theory","author":"D. Helmbold","year":"1992","unstructured":"Helmbold, D. and Warmuth, M., \u201cSome Weak Learning Results,\u201d inProc. 5th Annu. Workshop on Comput. Learning Theory, ACM Press, New York, NY, pp. 399\u2013412, 1992."},{"key":"BF03037231_CR26","doi-asserted-by":"crossref","unstructured":"Kearns, M. and Valiant, L., \u201cCryptographic Limitations on Learning Boolean Formulae and Finite Automata,\u201d in21th Annual Symposium on the Theory of Computing, ACM Press, 1989.","DOI":"10.1145\/73007.73049"},{"issue":"1","key":"BF03037231_CR27","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/174644.174647","volume":"41","author":"M. Kearns","year":"1994","unstructured":"Kearns, M. and Valiant, L., \u201cCryptographic Limitations on Learning Boolean Formulae and Finite Automata,\u201dJournal of the Association for Computing Machinery, 41, 1, pp. 67\u201395, 1994.","journal-title":"Journal of the Association for Computing Machinery"},{"key":"BF03037231_CR28","doi-asserted-by":"crossref","unstructured":"King, R. D., Muggleton, S., Lewis, R. A., and Sternberg, M. J. E., \u201cDrug Design by Machine Learning: The Use of Inductive Logic Programming to Model the Structure-Activity Relationships of Trimethoprim Analogues Binding to Dihydrofolate Reductase,\u201dProceedings of the National Academy of Science, 89, 1992.","DOI":"10.1073\/pnas.89.23.11322"},{"key":"BF03037231_CR29","doi-asserted-by":"crossref","unstructured":"Lassez, J-L., Maher, M. J., and Marriott, K., \u201cUnification Revisited,\u201d inFoundations of Deductive Databases and Logic Programming (Jack Minker, ed.), chapter 15, Morgan Kaufmann Publishers, pp. 587\u2013625, 1988.","DOI":"10.1016\/B978-0-934613-40-8.50019-1"},{"key":"BF03037231_CR30","volume-title":"Proceedings of the Twelfth National Conference on Artificial Intelligence","author":"S. Minton","year":"1994","unstructured":"Minton, S., \u201cSmall Is Beautiful: A Brute-Force Approach to Finding First-Order Formulas,\u201d inProceedings of the Twelfth National Conference on Artificial Intelligence, Seattle, Washington, MIT Press, 1994."},{"key":"BF03037231_CR31","unstructured":"Muggleton, S. H. and Page, C. D., \u201cA Learnability Model for Universal Representations,\u201d inProceedings of the Fourth International Workshop on Inductive Logic Programming (S. Wrobel, ed.), Sankt Augustin, Germany, pp. 139\u2013160, 1994. GMD. Published asGMD-Studien Nr. 237."},{"key":"BF03037231_CR32","first-page":"371","volume-title":"Proceedings of the Eleventh International Conference on Machine Learning (ML-94)","author":"S. Muggleton","year":"1994","unstructured":"Muggleton, S., \u201cBayesian Inductive Logic Programming,\u201d inProceedings of the Eleventh International Conference on Machine Learning (ML-94), San Francisco, Morgan Kaufmann, pp. 371\u2013379, 1994."},{"key":"BF03037231_CR33","doi-asserted-by":"crossref","unstructured":"Muggleton, S., \u201cBayesian Inductive Logic Programming,\u201d inProceedings of the Seventh Annual ACM Conference on Computational Learning Theory (COLT-94), New York, The Association for Computing Machinery, pp. 3\u201311, 1994.","DOI":"10.1145\/180139.178095"},{"key":"BF03037231_CR34","doi-asserted-by":"crossref","unstructured":"Nienhuys-Cheng, S. H. and Polman, M., \u201cSample Pac-Learnability in Model Inference,\u201d inMachine Learning: ECML-94, Catania, Italy,Lecture Notes in Computer Science #784, Springer-Verlag, 1994.","DOI":"10.1007\/3-540-57868-4_60"},{"key":"BF03037231_CR35","volume-title":"Second Int. Conf on Principles of Knowledge Representation and Reasoning","author":"C. D. Page","year":"1991","unstructured":"Page, C. D. and Frisch, A. M., \u201cGeneralizing Atoms in Constraint Logic,\u201d inSecond Int. Conf on Principles of Knowledge Representation and Reasoning (J. Allen, R. Fikes, and E. Sandewall, eds.), San Mateo, CA, Morgan Kaufmann, April 1991."},{"key":"BF03037231_CR36","first-page":"29","volume-title":"Inductive Logic Programming","author":"C. D. Page","year":"1992","unstructured":"Page, C. D. and Frisch, A. M., \u201cGeneralization and Learnability: A Study of Constrained Atoms,\u201d inInductive Logic Programming (S. H. Muggleton, eds.), Academic Press, London, pp. 29\u201361, 1992."},{"key":"BF03037231_CR37","unstructured":"Page, C. D., \u201cAnti-Unification in Constraint Logics: Foundations and Applications to Learnability in First-Order Logic, to Speed-up Learning, and to Deduction,\u201dPh.D thesis, University of Illinois at Urbana-Champaign, 1993."},{"issue":"4","key":"BF03037231_CR38","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., \u201cComputational Limitations on Learning from Examples,\u201dJournal of the ACM, 35, 4, pp. 965\u2013984, 1988.","journal-title":"Journal of the ACM"},{"key":"BF03037231_CR39","doi-asserted-by":"crossref","first-page":"430","DOI":"10.1016\/0022-0000(90)90028-J","volume":"41","author":"L. Pitt","year":"1990","unstructured":"Pitt, L. and Warmuth, M., \u201cPrediction-Preserving Reducibility,\u201dJournal of Computer and System Sciences, 41, pp. 430\u2013467, 1990.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF03037231_CR40","doi-asserted-by":"crossref","unstructured":"Plotkin, G. D., \u201cA Note on Inductive Generalization,\u201d inMachine Intelligence 5, Edinburgh University Press, pp. 153\u2013163, 1969.","DOI":"10.1017\/S0022226700002164"},{"key":"BF03037231_CR41","first-page":"3","volume":"5","author":"J. R. Quinlan","year":"1990","unstructured":"Quinlan, J. R., \u201cLearning Logical Definitions from Relations,\u201dMachine Learning, 5, 3, 1990.","journal-title":"Machine Learning"},{"key":"BF03037231_CR42","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1080\/08839519408945435","volume":"8","author":"P. Riddle","year":"1994","unstructured":"Riddle, P., Segal, R., and Etzioni, O., \u201cRepresentation Design and Brute-Force Induction in a Boeing Manufacturing Domain,\u201dApplied Artificial Intelligence, 8, pp. 125\u2013147, 1994.","journal-title":"Applied Artificial Intelligence"},{"key":"BF03037231_CR43","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1023\/A:1022678217288","volume":"14","author":"C. Rouveirol","year":"1994","unstructured":"Rouveirol, C., \u201cFlattening and Saturation: Two Representation Changes for Generalization,\u201dMachine Learning, 14, 2, 1994.","journal-title":"Machine Learning"},{"key":"BF03037231_CR44","first-page":"2","volume":"5","author":"R. Schapire","year":"1990","unstructured":"Schapire, R., \u201cThe Strength of Weak Learnability,\u201dMachine Learning, 5, 2, 1990.","journal-title":"Machine Learning"},{"key":"BF03037231_CR45","unstructured":"Srinivasan, A., Muggleton, S., King, R., and Sternberg, M., \u201cMutagenesis: Ilp Experiments in a Non-Determinate Biological Domain,\u201d inProceedings of the Fourth International Workshop on Inductive Logic Programming (S. Wrobel, ed.), Sankt Augustin, Germany, pp. 217\u2013232, 1994. GMD. Published asGMD-Studien Nr. 237."},{"key":"BF03037231_CR46","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G., \u201cA Theory of the Learnable,\u201dCommunications of the ACM, 27, 11, November 1984.","journal-title":"Communications of the ACM"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037231.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF03037231\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF03037231","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,24]],"date-time":"2023-05-24T22:11:02Z","timestamp":1684966262000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF03037231"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,12]]},"references-count":46,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[1995,12]]}},"alternative-id":["BF03037231"],"URL":"https:\/\/doi.org\/10.1007\/bf03037231","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"value":"0288-3635","type":"print"},{"value":"1882-7055","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,12]]}}}