{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T07:02:12Z","timestamp":1761807732526},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540566021"},{"type":"electronic","value":"9783540475972"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1993]]},"DOI":"10.1007\/3-540-56602-3_131","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T06:20:53Z","timestamp":1330237253000},"page":"115-123","source":"Crossref","is-referenced-by-count":26,"title":["Some lower bounds for the computational complexity of inductive logic programming"],"prefix":"10.1007","author":[{"given":"J\u00f6rg-Uwe","family":"Kietz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,1]]},"reference":[{"key":"8_CR1","unstructured":"M. Anthony and N.Biggs. Computational Learning Theory. Cambridge University Press, 1992."},{"key":"8_CR2","unstructured":"L. de Raedt and M. Bruynooghe. An overview of the interactive concept-learner and theory revisor clint. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992."},{"key":"8_CR3","doi-asserted-by":"crossref","unstructured":"S. D\u017eeroski, S. Muggleton, and S. Russell. Pac-learnability of determinate logic programs. In Proc. of the 5th ACM Workshop on Computaional Learning Theory (COLT), 1992.","DOI":"10.1145\/130385.130399"},{"key":"8_CR4","volume-title":"Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"Michael R. Garey and David S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. Freeman, San Francisco, Cal., 1979."},{"issue":"1","key":"8_CR5","first-page":"7","volume":"4","author":"D. Haussler","year":"1989","unstructured":"David Haussler. Learning conjunctive concepts in structural domains. Machine Learning, 4(1):7\u201340, 1989.","journal-title":"Machine Learning"},{"key":"8_CR6","unstructured":"J\u00f6rg-Uwe Kietz and Stefan Wrobel. Controlling the complexity of learning through syntactic and task-oriented models. In S. Muggleton, editor, Inductive Logic Programming, pages 107\u2013126. Academic Press, 1992."},{"key":"8_CR7","unstructured":"Stephan Muggleton and Cao Feng. Efficient induction of logic programs. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992."},{"key":"8_CR8","volume-title":"Machine invention of first-order predicates by inverting resolution","author":"S. Muggleton","year":"1988","unstructured":"Stephen Muggleton and Wray Buntine. Machine invention of first-order predicates by inverting resolution. In Proc. Fifth Intern. Conf. on Machine Learning, Los Altos, CA, 1988. Morgan Kaufman."},{"key":"8_CR9","unstructured":"C. D. Page and A. M. Frisch. Generalisation and learnability: a study in constained atoms. In S. Muggleton, editor, Inductive Logic Programming. Academic Press, 1992."},{"key":"8_CR10","unstructured":"Gordon D. Plotkin. A further note on inductive generalization. In B. Meltzer and D. Michie, editors, Machine Intelligence, volume 6, chapter 8, pages 101\u2013124. American Elsevier, 1971."},{"issue":"3","key":"8_CR11","first-page":"239","volume":"5","author":"J. R. Quinlan","year":"1990","unstructured":"J. R. Quinlan. Learning logical definitions from relations. Machine Learning, 5(3):239\u2013266, 1990.","journal-title":"Machine Learning"},{"key":"8_CR12","doi-asserted-by":"crossref","unstructured":"J. R. Quinlan. Determinate literals in inductive logic programming. In Proc. of the 12th IJCAI, 1991.","DOI":"10.1016\/B978-1-55860-200-7.50091-X"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Celine Rouveirol. Completness for inductive procedures. In Proc. Eigth Intern. Workshop on Machine Learning, pages 452\u2013456, 1991.","DOI":"10.1016\/B978-1-55860-200-7.50093-3"},{"key":"8_CR14","unstructured":"Celine Rouveirol. Semantic model for induction of first order theories. In Proc. 12th International Joint Conference on Artificial Intelligence, 1991."},{"key":"8_CR15","first-page":"129","volume-title":"Informatik-Fachberichte Nr. 152","author":"S. Wrobel","year":"1987","unstructured":"Stefan Wrobel. Higher-order concepts in a tractable knowledge representation. In K. Morik, editor, GWAI-87 11th German Workshop on Artificial Intelligence, Informatik-Fachberichte Nr. 152, pages 129\u2013138, Berlin, New York, Tokyo, October 1987. Springer."}],"container-title":["Lecture Notes in Computer Science","Machine Learning: ECML-93"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56602-3_131.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T16:04:45Z","timestamp":1605629085000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56602-3_131"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993]]},"ISBN":["9783540566021","9783540475972"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-56602-3_131","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1993]]}}}