{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T22:11:03Z","timestamp":1605651063345},"publisher-location":"Berlin, Heidelberg","reference-count":32,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540635147","type":"print"},{"value":"9783540695875","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3540635149_31","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T23:28:14Z","timestamp":1330298894000},"page":"17-32","source":"Crossref","is-referenced-by-count":6,"title":["On the complexity of some Inductive Logic Programming problems"],"prefix":"10.1007","author":[{"given":"Georg","family":"Gottlob","sequence":"first","affiliation":[]},{"given":"Nicola","family":"Leone","sequence":"additional","affiliation":[]},{"given":"Francesco","family":"Scarcello","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,7,10]]},"reference":[{"key":"2_CR1","doi-asserted-by":"crossref","first-page":"1021","DOI":"10.1126\/science.7973651","volume":"266","author":"L.M. Adleman","year":"1994","unstructured":"L.M. Adleman. Molecular Computation of Solutions to Combinatorial Problems. Science 266, pp. 1021\u20131024, 1994.","journal-title":"Science"},{"key":"2_CR2","unstructured":"L. D. Baxter. The NP-completeness of Subsumption. Unpublished manuscript, 1977."},{"key":"2_CR3","unstructured":"P. Cholewinski, V.W. Marek, and M. Truszczynski Default Reasoning System DeReS Proc. Fifth Intl. Conference on Principles of Knowledge Representation and Reasoning (KR'96), Cambridge, MA, Nov.5\u20138, 1996."},{"key":"2_CR4","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1613\/jair.97","volume":"2","author":"W. Cohen","year":"1995","unstructured":"W. Cohen. PAC-Learning Recursive Logic Programs: Efficient Algorithms. Journal of Artificial Intelligence Research, 2: 501\u2013539, 1995.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"2_CR5","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1613\/jair.1917","volume":"2","author":"W. Cohen","year":"1995","unstructured":"W. Cohen. PAC-Learning Recursive Logic Programs: Negative Results. Journal of Artificial Intelligence Research, 2: 541\u2013573, 1995.","journal-title":"Journal of Artificial Intelligence Research"},{"issue":"3-4","key":"2_CR6","doi-asserted-by":"crossref","first-page":"369","DOI":"10.1007\/BF03037231","volume":"13","author":"W. Cohen","year":"1995","unstructured":"W. Cohen and C. D. Page. Polynomial Learnability and Inductive Logic Programming \u2014 Methods and Results. New Generation Computing, 13(3-4): 369\u2013409, 1995.","journal-title":"New Generation Computing"},{"key":"2_CR7","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0004-3702(94)90112-0","volume":"70","author":"L. Raedt De","year":"1994","unstructured":"L. De Raedt and S. D\u017eeroski. First order jk-clausal theories are PAC-learnable. Artificial Intelligence, 70: 375\u2013392, 1994.","journal-title":"Artificial Intelligence"},{"key":"2_CR8","series-title":"Proc. Second Intl. workshop on Logic Programming and Nonmonotonic reasoning (LPNMR-93)","first-page":"43","volume-title":"Implementing Semantics of Disjunctive Logic programs Using Fringes and Abstract properties","author":"J. Dix","year":"1993","unstructured":"J. Dix and M. M\u00fcller. Implementing Semantics of Disjunctive Logic programs Using Fringes and Abstract properties. Proc. Second Intl. workshop on Logic Programming and Nonmonotonic reasoning (LPNMR-93), Lisbon, Portugal, July 1993, pp. 43\u201359, MIT Press."},{"issue":"3\/4","key":"2_CR9","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1007\/BF01536399","volume":"15","author":"T. Eiter","year":"1995","unstructured":"T. Eiter and G. Gottlob. On the Computational Cost of Disjunctive Logic Programming: Propositional Case. Annals of Mathematics and Artificial Intelligence, 15(3\/4):289\u2013323, 1995.","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2_CR10","unstructured":"T. Eiter, N. Leone, C. Mateis, G. Pfeifer, and F. Scarcello. A Deductive System for Nonmonotonic Reasoning. In Proc. 4th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR '97), Lecture Notes in AI (LNAI), J. Dix, U. Furbach, and A. Nerode Eds., Springer, Berlin, 1997 (to appear).","DOI":"10.1007\/3-540-63255-7_27","doi-asserted-by":"crossref"},{"key":"2_CR11","unstructured":"T. Eiter, G. Gottlob, and H. Mannila.Disjunctive Datalog. ACM Trans. on Database Syst., September 1997. To appear.","DOI":"10.1145\/261124.261126","doi-asserted-by":"crossref"},{"key":"2_CR12","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson. Computers and Intractability \u2014 A guide to the Theory of NP-completeness. Freman, San Francisco, CA, 1979.","volume-title":"Computers and Intractability \u2014 A guide to the Theory of NP-completeness"},{"key":"2_CR13","author":"M. Gelfond","first-page":"1070","year":"1988","unstructured":"M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Logic Programming: Proc. Fifth Intl Conference and Symposium, pp. 1070\u20131080, Cambridge, Mass., 1988. MIT Press.","volume-title":"Logic Programming: Proc. Fifth Intl Conference and Symposium"},{"key":"2_CR14","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0019-9958(67)91165-5","volume":"10","author":"E. M. Gold","year":"1967","unstructured":"E. M. Gold. Language Identification in the Limit. Information and Control, 10:447\u2013474, 1967.","journal-title":"Information and Control"},{"key":"2_CR15","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/0020-0190(87)90103-7","volume":"24","author":"G. Gottlob","year":"1987","unstructured":"G. Gottlob. Subsumption and Implication. Information Processing Letters, 24:109\u2013111, 1987.","journal-title":"Information Processing Letters"},{"issue":"3","key":"2_CR16","doi-asserted-by":"crossref","first-page":"397","DOI":"10.1093\/logcom\/2.3.397","volume":"2","author":"G. Gottlob","year":"1992","unstructured":"G. Gottlob. Complexity Results for Nonmonotonic Logics. J. Logic and Computation, 2(3):397\u2013425, June 1992.","journal-title":"J. Logic and Computation"},{"key":"2_CR17","author":"D. S. Johnson","year":"1990","unstructured":"D. S. Johnson. A Catalog of Complexity Classes. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, volume A, chapter 2. Elsevier Science Publishers B.V. (North-Holland), 1990.","volume-title":"Handbook of Theoretical Computer Science"},{"issue":"1","key":"2_CR18","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1145\/181668.181674","volume":"5","author":"J.U. Kietz","year":"1994","unstructured":"J.U. Kietz and S. D\u017eeroski. Inductive logic programming and learnability. SIGART Bulletin 5(1): 22\u201332 (Special issue on Inductive Logic Programming), 1994.","journal-title":"SIGART Bulletin"},{"issue":"2","key":"2_CR19","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/0004-3702(88)90002-1","volume":"36","author":"D. Haussler","year":"1988","unstructured":"D. Haussler. Quantifying inductive bias: AI learning algorithms and Valiant's model. Artificial Intelligence, 36(2):177\u2013221, 1988.","journal-title":"Artificial Intelligence"},{"key":"2_CR20","unstructured":"R.J. Lipton. Using DNA to solve NP-complete Problems. Priceton University."},{"issue":"3","key":"2_CR21","doi-asserted-by":"crossref","first-page":"588","DOI":"10.1145\/116825.116836","volume":"38","author":"W. Marek","year":"1991","unstructured":"W. Marek and M. Truszczy\u0144ski. Autoepistemic Logic. JACM, 38(3):588\u2013619, 1991.","journal-title":"JACM"},{"issue":"4","key":"2_CR22","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/BF03037089","volume":"8","author":"S. H. Muggleton","year":"1991","unstructured":"S. H. Muggleton. Inductive Logic Programming. New Generation Computing, 8(4):295\u2013318, 1991.","journal-title":"New Generation Computing"},{"key":"2_CR23","year":"1992","unstructured":"Inductive Logic Programming, S. H. Muggleton ed., Academic Press, London, 1992.","volume-title":"Inductive Logic Programming"},{"issue":"20","key":"2_CR24","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1016\/0743-1066(94)90035-3","volume":"19","author":"S. H. Muggleton","year":"1994","unstructured":"S. H. Muggleton and L. De Raedt. Inductive Logic Programming: Theory and Methods. Journal of Logic Programming, 19,20:629\u2013679, 1994.","journal-title":"Journal of Logic Programming"},{"key":"2_CR25","author":"S. Muggleton","first-page":"139","year":"1994","unstructured":"Muggleton, S., and Page, D., A learnability model for universal representations. In Proc. Fourth International Workshop on Inductive Logic Programming, pages 139\u2013160. GMD, Bonn, 1994.","volume-title":"Proc. Fourth International Workshop on Inductive Logic Programming"},{"key":"2_CR26","author":"C. D. Page","first-page":"29","year":"1992","unstructured":"C. D. Page and A. M. Frish. Generalization and Learnability: a study of constrained atoms. In Inductive Logic Programming, pp.29\u201361, S. H. Muggleton ed., Academic Press, London, 1992.","volume-title":"Inductive Logic Programming"},{"key":"2_CR27","unstructured":"G. D. Plotkin. A note on Inductive Generalization. In Machine Intelligence, pp. 153\u2013163, B. Meltzer and D. Michie eds., American Elsevier, 1970."},{"key":"2_CR28","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/0004-3702(80)90014-4","volume":"13","author":"R. Reiter","year":"1980","unstructured":"R. Reiter. A Logic for Default Reasoning. Artificial Intelligence, 13:81\u2013132, 1980.","journal-title":"Artificial Intelligence"},{"issue":"1","key":"2_CR29","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/321250.321253","volume":"12","author":"J. Robinson","year":"1965","unstructured":"J. Robinson. A machine-oriented logic based on the resolution principle. Journal of the ACM, 12(1):23\u201341, 1965.","journal-title":"Journal of the ACM"},{"key":"2_CR30","first-page":"197","volume":"5","author":"R. E. Schapire","year":"1990","unstructured":"R. E. Schapire. The Strength of Weak Learnability. Machine Learning, 5:197\u2013227, 1990.","journal-title":"Machine Learning"},{"issue":"2","key":"2_CR31","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1006\/inco.1996.0094","volume":"131","author":"D. Rooi\u00df","year":"1996","unstructured":"Diana Rooi\u00df and Klaus Wagner. On the Power of DNA Computation. Information and Computation, 131(2):95\u2013109, 1996.","journal-title":"Information and Computation"},{"key":"2_CR32","unstructured":"L. G. Valiant. A Theory of the Learnable. Communications of the ACM, 27:1134\u20131142.","DOI":"10.1145\/1968.1972","doi-asserted-by":"crossref"}],"container-title":["Inductive Logic Programming","Lecture Notes in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3540635149_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:18:36Z","timestamp":1605647916000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540635147","9783540695875"],"references-count":32,"URL":"http:\/\/dx.doi.org\/10.1007\/3540635149_31","relation":{"cites":[]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}]}}