{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:31:21Z","timestamp":1759638681202},"reference-count":66,"publisher":"Elsevier BV","issue":"1-2","license":[{"start":{"date-parts":[[2001,5,1]],"date-time":"2001-05-01T00:00:00Z","timestamp":988675200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"},{"start":{"date-parts":[[2013,7,25]],"date-time":"2013-07-25T00:00:00Z","timestamp":1374710400000},"content-version":"vor","delay-in-days":4468,"URL":"https:\/\/www.elsevier.com\/open-access\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Artificial Intelligence"],"published-print":{"date-parts":[[2001,5]]},"DOI":"10.1016\/s0004-3702(01)00062-5","type":"journal-article","created":{"date-parts":[[2002,7,25]],"date-time":"2002-07-25T21:53:17Z","timestamp":1027633997000},"page":"31-97","source":"Crossref","is-referenced-by-count":16,"title":["Learning logic programs with structured background knowledge\u2606\u2606An extended abstract of this paper appeared in: L.\u00a0De Raedt (Ed.), Proceedings of the Fifth International Workshop on Inductive Logic Programming, Tokyo, Japan, 1995, pp. 53\u201376, Scientific Report of the Department of Computer Science, Katholieke Universiteit Leuven, and also in the post-conference volume: L.\u00a0De Raedt (Ed.), Advances in Inductive Logic Programming, IOS Press, Amsterdam\/Ohmsha, Tokyo, 1996, pp. 172\u2013191."],"prefix":"10.1016","volume":"128","author":[{"given":"Tam\u00e1s","family":"Horv\u00e1th","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gy\u00f6rgy","family":"Tur\u00e1n","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0004-3702(01)00062-5_BIB001","series-title":"Learning propositional Horn sentences with hints","author":"Angluin","year":"1987"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB002","series-title":"Proc. 8th International Workshop on Algorithmic Learning Theory (ALT-97)","first-page":"432","article-title":"Learning acyclic first-order Horn sentences from entailment","volume":"1316","author":"Arimura","year":"1997"},{"issue":"4","key":"10.1016\/S0004-3702(01)00062-5_BIB003","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","article-title":"Learnability and the Vapnik\u2013Chervonenkis dimension","volume":"36","author":"Blumer","year":"1989","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB004","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(88)90001-X","article-title":"Generalized subsumption and its application to induction and redundancy","volume":"36","author":"Buntine","year":"1988","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB005","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0004-3702(94)00034-4","article-title":"PAC-learning non-recursive Prolog clauses","volume":"79","author":"Cohen","year":"1995","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB006","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1613\/jair.97","article-title":"PAC-learning recursive logic programs: Efficient algorithms","volume":"2","author":"Cohen","year":"1995","journal-title":"J. Artificial Intelligence Res."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB007","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1613\/jair.1917","article-title":"PAC-learning recursive logic programs: Negative results","volume":"2","author":"Cohen","year":"1995","journal-title":"J. Artificial Intelligence Res."},{"issue":"2\/3","key":"10.1016\/S0004-3702(01)00062-5_BIB008","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1023\/A:1022619701011","article-title":"The learnability of description logics with equality constraints","volume":"17","author":"Cohen","year":"1994","journal-title":"Machine Learning"},{"issue":"3\u20134","key":"10.1016\/S0004-3702(01)00062-5_BIB009","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF03037231","article-title":"Polynomial learnability and inductive logic programming: Methods and results","volume":"13","author":"Cohen","year":"1995","journal-title":"New Generation Computing, Special Issue on Inductive Logic Programming"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB010","series-title":"Proc. 12th Annual IEEE Conference on Computational Complexity, Ulm, Germany","first-page":"82","article-title":"Complexity and expressive power of logic programming","author":"Dantsin","year":"1997"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB011","series-title":"Introduction to Lattices and Order","author":"Davey","year":"1990"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB012","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/S0004-3702(97)00041-6","article-title":"Logical settings for concept-learning","volume":"95","author":"De Raedt","year":"1997","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB013","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(94)90112-0","article-title":"First order jk-clausal theories are PAC-learnable","volume":"70","author":"De Raedt","year":"1994","journal-title":"Artificial Intelligence"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB014","series-title":"Proc. 5th Annual ACM Workshop on Computational Learning Theory (COLT-92)","first-page":"128","article-title":"PAC-learnability of determinate logic programs","author":"D\u017eeroski","year":"1992"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB015","series-title":"Finite Model Theory","author":"Ebbinghaus","year":"1995"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB016","series-title":"Matters Horn and other features in the computational learning theory landscape: The notion of membership, Ph.D. Thesis","author":"Frazier","year":"1994"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB017","series-title":"Proc. 10th International Conference Machine Learning, Amherst, MA","first-page":"120","article-title":"Learning from entailment: An application to propositional Horn sentences","author":"Frazier","year":"1993"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB018","doi-asserted-by":"crossref","first-page":"151","DOI":"10.1023\/A:1026443024002","article-title":"CLASSIC learning","volume":"25","author":"Frazier","year":"1996","journal-title":"Machine Learning"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB019","series-title":"Complexity of learning from one-sided examples","author":"Ger\u00e9b-Grauss","year":"1989"},{"issue":"2","key":"10.1016\/S0004-3702(01)00062-5_BIB020","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","article-title":"Subsumption and implication","volume":"24","author":"Gottlob","year":"1987","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB021","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/0166-218X(92)90294-K","article-title":"Polynomial graph-colorings","volume":"35","author":"Gutjahr","year":"1992","journal-title":"Discrete Appl. Math."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB022","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1007\/BF02122553","article-title":"On multiplicative graphs and the product conjecture","volume":"8","author":"H\u00e4ggkvist","year":"1988","journal-title":"Combinatorica"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB023","series-title":"An Introduction to the Theory of Numbers","author":"Hardy","year":"1979"},{"issue":"1","key":"10.1016\/S0004-3702(01)00062-5_BIB024","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1007\/BF00114802","article-title":"Learning conjunctive concepts in structural domains","volume":"4","author":"Haussler","year":"1989","journal-title":"Machine Learning"},{"issue":"2","key":"10.1016\/S0004-3702(01)00062-5_BIB025","doi-asserted-by":"crossref","first-page":"129","DOI":"10.1016\/0890-5401(91)90042-Z","article-title":"Equivalence of models for polynomial learnability","volume":"95","author":"Haussler","year":"1991","journal-title":"Inform. and Comput."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB026","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1016\/0012-365X(94)90235-6","article-title":"Homomorphisms to oriented paths","volume":"132","author":"Hell","year":"1994","journal-title":"Discrete Math."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB027","series-title":"Model Theory","author":"Hodges","year":"1993"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB028","series-title":"Proc. 9th International Workshop on Inductive Logic Programming","first-page":"128","article-title":"Application of different learning methods to Hungarian part-of-speech tagging","volume":"1634","author":"Horv\u00e1th","year":"1999"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB029","series-title":"Proc. 10th Annual Conference on Computational Learning Theory (COLT-97), Nashville, TN","first-page":"10","article-title":"Learning logic programs by using the product homomorphism method","author":"Horv\u00e1th","year":"1997"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB030","series-title":"Proc. 6th International Workshop on Inductive Logic Programming (ILP-96)","first-page":"315","article-title":"Learning logic programs with random classification noise","volume":"1314","author":"Horv\u00e1th","year":"1997"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB031","series-title":"Advances in Inductive Logic Programming","first-page":"172","article-title":"Learning logic programs with structured background knowledge","author":"Horv\u00e1th","year":"1996"},{"issue":"6","key":"10.1016\/S0004-3702(01)00062-5_BIB032","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1145\/293347.293351","article-title":"Efficient noise-tolerant learning from statistical queries","volume":"45","author":"Kearns","year":"1998","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB033","series-title":"An Introduction to Computational Learning Theory","author":"Kearns","year":"1994"},{"issue":"3","key":"10.1016\/S0004-3702(01)00062-5_BIB034","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1023\/A:1007610422992","article-title":"Learning function-free Horn expressions","volume":"37","author":"Khardon","year":"1999","journal-title":"Machine Learning"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB035","series-title":"Proc. European Conference on Machine Learning (ECML-93)","first-page":"115","article-title":"Some lower bounds for the computational complexity of inductive logic programming","volume":"667","author":"Kietz","year":"1993"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB036","series-title":"Induktive Analyse Relationaler Daten, Ph.D. Thesis","author":"Kietz","year":"1996"},{"issue":"1","key":"10.1016\/S0004-3702(01)00062-5_BIB037","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/181668.181674","article-title":"Inductive logic programming and learnability","volume":"5","author":"Kietz","year":"1994","journal-title":"SIGART Bull."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB038","series-title":"The Art of Computer Programming, Vol. 2: Seminumerical Algorithms","author":"Knuth","year":"1981"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB039","series-title":"Inductive Logic Programming: Techniques and Applications","author":"Lavra\u010d","year":"1994"},{"issue":"5","key":"10.1016\/S0004-3702(01)00062-5_BIB040","doi-asserted-by":"crossref","first-page":"911","DOI":"10.1137\/0220056","article-title":"Learning simple concept under simple distributions","volume":"20","author":"Li","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB041","series-title":"Foundations of Logic Programming","author":"Lloyd","year":"1987"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB042","series-title":"Combinatorial Problems and Exercises","author":"Lov\u00e1sz","year":"1979"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB043","series-title":"Proc. Bar-Ilan Symposium on the Foundations of Artificial Intelligence (BISFAI-95)","first-page":"75","article-title":"On learnability and predicate logic","author":"Maass","year":"1995"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB044","series-title":"Elements of Scientific Inquiry","author":"Martin","year":"1999"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB045","series-title":"Handbook of Number Theory","volume":"351","author":"Mitrinovi\u0107","year":"1996"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB046","series-title":"Proc. 1st Conference on Algorithmic Learning Theory, Ohmsma, Tokyo, Japan","first-page":"43","article-title":"Inductive logic programming","author":"Muggleton","year":"1990"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB047","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/0743-1066(94)90035-3","article-title":"Inductive logic programming: Theory and methods","volume":"19\/20","author":"Muggleton","year":"1994","journal-title":"J. Logic Programming"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB048","series-title":"Inductive Logic Programming","first-page":"281","article-title":"Efficient induction in logic programs","author":"Muggleton","year":"1992"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB049","series-title":"Proc. ACM Symposium on Theory of Computing (STOC-87)","first-page":"296","article-title":"On learning boolean functions","author":"Natarajan","year":"1987"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB050","series-title":"Machine Learning: A Theoretical Approach","author":"Natarajan","year":"1991"},{"issue":"2","key":"10.1016\/S0004-3702(01)00062-5_BIB051","doi-asserted-by":"crossref","first-page":"328","DOI":"10.1137\/0220021","article-title":"Probably approximate learning of sets and functions","volume":"20","author":"Natarajan","year":"1991","journal-title":"SIAM J. Comput."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB052","first-page":"187","article-title":"On classes of relations and graphs determined by subobjects and factorobjetcs","volume":"22","author":"Ne\u0161et\u0159il","year":"1979","journal-title":"Discrete Math."},{"key":"10.1016\/S0004-3702(01)00062-5_BIB053","series-title":"Foundations of Inductive Logic Programming","volume":"1228","author":"Nienhuys-Cheng","year":"1997"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB054","series-title":"Inductive Logic Programming","first-page":"29","article-title":"Generalization and learnability: A study of constrained atoms","author":"Page","year":"1992"},{"issue":"4","key":"10.1016\/S0004-3702(01)00062-5_BIB055","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","article-title":"Computational limitations on learning from examples","volume":"35","author":"Pitt","year":"1988","journal-title":"J. ACM"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB056","series-title":"Machine Intelligence, Vol. 5","first-page":"153","article-title":"A note on inductive generalization","author":"Plotkin","year":"1970"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB057","series-title":"Machine Intelligence, Vol. 6","first-page":"101","article-title":"A further note on inductive generalization","author":"Plotkin","year":"1971"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB058","series-title":"Algorithmes de compl\u00e9tion et g\u00e9n\u00e9ralisation en logique du premier ordre, Ph.D. Thesis","author":"Pottier","year":"1989"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB059","series-title":"Generalisation de termes en theorie equationnelle. Cas associatif-commutatif","author":"Pottier","year":"1989"},{"issue":"3","key":"10.1016\/S0004-3702(01)00062-5_BIB060","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1023\/A:1007421315813","article-title":"Learning from examples and membership queries with structured determinations","volume":"32","author":"Tadepalli","year":"1998","journal-title":"Machine Learning"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB061","series-title":"Proc. 11th Annual Conference on Computational Learning Theory (COLT-98), Madison, WI","first-page":"166","article-title":"Learning atomic formulas with prescribed properties","author":"Tsapara","year":"1998"},{"issue":"11","key":"10.1016\/S0004-3702(01)00062-5_BIB062","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","article-title":"A theory of the learnable","volume":"27","author":"Valiant","year":"1985","journal-title":"Comm. ACM"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB063","series-title":"Proc. ACM Symposium on Theory of Computing (STOC-99)","first-page":"642","article-title":"Robust logics","author":"Valiant","year":"1999"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB064","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1002\/jgt.3190150503","article-title":"Multiplicativity, Part I. Variations, multiplicative graphs and digraphs","volume":"15","author":"Zhou","year":"1991","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB065","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1002\/jgt.3190150504","article-title":"Multiplicativity, Part II. Nonmultiplicative digraphs and characterization of oriented paths","volume":"15","author":"Zhou","year":"1991","journal-title":"J. Graph Theory"},{"key":"10.1016\/S0004-3702(01)00062-5_BIB066","series-title":"Foundations of Deductive Databases and Logic Programming","first-page":"587","article-title":"Unification revisited","author":"Lassez","year":"1987"}],"container-title":["Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370201000625?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0004370201000625?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,1,28]],"date-time":"2020-01-28T18:25:20Z","timestamp":1580235920000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0004370201000625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001,5]]},"references-count":66,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2001,5]]}},"alternative-id":["S0004370201000625"],"URL":"https:\/\/doi.org\/10.1016\/s0004-3702(01)00062-5","relation":{},"ISSN":["0004-3702"],"issn-type":[{"value":"0004-3702","type":"print"}],"subject":[],"published":{"date-parts":[[2001,5]]}}}