{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T23:10:23Z","timestamp":1742598623828,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":33,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540594871"},{"type":"electronic","value":"9783540492825"}],"license":[{"start":{"date-parts":[[1995,1,1]],"date-time":"1995-01-01T00:00:00Z","timestamp":788918400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-59487-6_1","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:18:25Z","timestamp":1330276705000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Complexity results for abductive logic programming"],"prefix":"10.1007","author":[{"given":"Thomas","family":"Eiter","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Georg","family":"Gottlob","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nicola","family":"Leone","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,31]]},"reference":[{"key":"1_CR1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1016\/B978-0-934613-40-8.50006-3","volume-title":"Foundations of Deductive Databases and Logic Programming","author":"K. Apt","year":"1988","unstructured":"K. Apt, H. Blair, and A. Walker. Towards a Theory of Declarative Knowledge. In J. Minker, editor, Foundations of Deductive Databases and Logic Programming, pages 89\u2013148. Morgan Kaufman, Washington DC, 1988."},{"key":"1_CR2","first-page":"72","volume":"19\u201320","author":"C. Baral","year":"1994","unstructured":"C. Baral and M. Gelfond. Logic Programming and Knowledge Representation Journal of Logic Programming, 19\u201320:72\u2013144, 1994.","journal-title":"Journal of Logic Programming"},{"key":"1_CR3","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/0890-5401(91)90073-B","volume":"19","author":"N. Bidoit","year":"1991","unstructured":"N. Bidoit and C. Froidevaux. General Logic Databases and Programs: Default Semantics and Stratification. Information and Computation, 19:15\u201354, 1991.","journal-title":"Information and Computation"},{"issue":"5","key":"1_CR4","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1093\/logcom\/1.5.661","volume":"1","author":"L. Console","year":"1991","unstructured":"L. Console, D. Theseider Dupr\u00e9, and P. Torasso. On the Relationship Between Abduction and Deduction. Journal of Logic and Computation, 1(5):661\u2013690, 1991.","journal-title":"Journal of Logic and Computation"},{"key":"1_CR5","unstructured":"M. Denecker and D. De Schreye. SLDNFA: an abductive procedure for normal abductive logic programs. In Proc. JICSLP-92, pp. 686\u2013700, 1992."},{"key":"1_CR6","unstructured":"M. Denecker and D. De Schreye. Representing incomplete knowledge in abductive logic programming. In Proc. ILPS-93, pp. 147\u2013163, 1993."},{"key":"1_CR7","unstructured":"P. Dung. Negation as Hypotheses: An Abductive Foundation for Logic Programming. In Proc. ICLP-91. MIT Press, 1991."},{"key":"1_CR8","doi-asserted-by":"crossref","unstructured":"T. Eiter and G. Gottlob. The Complexity of Logic-Based Abduction. JACM, 1995. Extended abstract Proc. STACS-93, LNCS 665, 70\u201379.","DOI":"10.1007\/3-540-56503-5_10"},{"key":"1_CR9","unstructured":"T. Eiter, G. Gottlob and N. Leone. Abduction from Logic Programs: Semantics and Complexity. TR 94-72 Christian Doppler Lab for Expert Systems, 1994."},{"key":"1_CR10","unstructured":"K. Eshghi and R. Kowalski. Abduction Compared with Negation as Failure. In Proc. ICLP-89, pp. 234\u2013254. MIT Press, 1989."},{"key":"1_CR11","unstructured":"K. Eshghi. A Tractable Class of Abduction Problems. In Proc. IJCA1-93, pp. 3\u20138."},{"key":"1_CR12","first-page":"1070","volume-title":"The Stable Model Semantics for Logic Programming","author":"M. Gelfond","year":"1988","unstructured":"M. Gelfond and V. Lifschitz. The Stable Model Semantics for Logic Programming. In Proc. Fifth Conference and Symposium on Logic Programming, B. Kowalski and R. Bowen (eds), pp. 1070\u20131080, Cambridge Mass., 1988. MIT Press."},{"key":"1_CR13","unstructured":"K. Inoue. Extended logic programs with default assumptions. In Proc. ICLP-91, pp. 490\u2013504."},{"key":"1_CR14","unstructured":"K. Inoue. Studies on Abductive and Nonmonotonic Reasoning. PhD thesis, Kyoto University, 1992."},{"key":"1_CR15","unstructured":"N. Iwayama and K. Satoh. Computing abduction using the TMS. In Proc. ICLP-91, pp. 505\u2013518, 1991."},{"key":"1_CR16","first-page":"445","volume":"17","author":"J. Josephson","year":"1987","unstructured":"J. Josephson, B. Chandrasekaran, J. J. W. Smith, and M. Tanner. A Mechanism for Forming Composite Explanatory Hypotheses. IEEE TSMC17:445\u2013454, 1987.","journal-title":"IEEE TSMC"},{"issue":"6","key":"1_CR17","doi-asserted-by":"crossref","first-page":"719","DOI":"10.1093\/logcom\/2.6.719","volume":"2","author":"A. Kakas","year":"1992","unstructured":"A. Kakas and R. Kowalski and F. Toni. Abductive logic programming. Journal of Logic and Computation, 2(6):719\u2013771, 1992.","journal-title":"Journal of Logic and Computation"},{"key":"1_CR18","unstructured":"A. Kakas and P. Mancarella. Generalized Stable Models: a Semantics for Abduction. In Proc. ECAI-90, pp. 385\u2013391, 1990."},{"key":"1_CR19","unstructured":"A. Kakas and P. Mancarella. Stable theories for logic programs. In Proc. ISLP-91, pp. 88\u2013100, 1991."},{"key":"1_CR20","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/0004-3702(92)90073-7","volume":"53","author":"K. Konolige","year":"1992","unstructured":"K. Konolige. Abduction versus closure in causal theories. Artificial Intelligence, 53:255\u2013272, 1992.","journal-title":"Artificial Intelligence"},{"key":"1_CR21","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-96826-6","volume-title":"Foundations of Logic Programming","author":"J. Lloyd","year":"1984","unstructured":"J. Lloyd. Foundations of Logic Programming. Springer, Berlin, 1984."},{"key":"1_CR22","doi-asserted-by":"crossref","unstructured":"J. Lobo, J. Minker, and A. Rajasekar. Foundations of Disjunctive Logic Programming. MIT Press, 1992.","DOI":"10.1016\/B978-0-12-450010-5.50022-0"},{"key":"1_CR23","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:588\u2013619, 1991.","journal-title":"JACM"},{"key":"1_CR24","first-page":"37","volume-title":"Computing Intersection of Autoepistemic Expansions","author":"W. Marek","year":"1991","unstructured":"W. Marek and M. Truszczy\u0144ski. Computing Intersection of Autoepistemic Expansions. In A. Nerode, W. Marek, and V. Subrahmanian, editors, Proc. LPNMR-91, pp. 37\u201350, Washington DC, July 1991. MIT Press."},{"key":"1_CR25","doi-asserted-by":"crossref","unstructured":"J. Minker. On Indefinite Data Bases and the Closed World Assumption. In Proc. of the 6th Conference on Automated Deduction (CADE-82), pp. 292\u2013308, 1982.","DOI":"10.1007\/BFb0000066"},{"key":"1_CR26","unstructured":"C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"1_CR27","doi-asserted-by":"crossref","unstructured":"Y. Peng and J. Reggia. Abductive Inference Models for Diagnostic Problem Solving. Springer, 1990.","DOI":"10.1007\/978-1-4419-8682-5"},{"key":"1_CR28","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/BF03037171","volume":"9","author":"T. Przymusinski","year":"1991","unstructured":"T. Przymusinski. Stable Semantics for Disjunctive Programs. New Generation Computing, 9:401\u2013424, 1991.","journal-title":"New Generation Computing"},{"key":"1_CR29","unstructured":"D. Sacc\u00e0. The Expressive Power of Stable Models for DATALOG Queries with Negation. H. Blair, W. Marek, A. Nerode, and J. Remmel (eds), Proc. of the Second Workshop on Structural Complexity and Recursion-Theoretic Methods in Logic Programming, pp. 150\u2013162. Cornell University, Math. Sciences Institute, 1993."},{"key":"1_CR30","doi-asserted-by":"crossref","unstructured":"J. Schlipf. The Expressive Powers of Logic Programming Semantics. Proc. ACM PODS-90, pp. 196\u2013204. Extended version to appear in JCSS.","DOI":"10.1145\/298514.298564"},{"key":"1_CR31","unstructured":"C. Sakama and K. Inoue. On the Equivalence between Disjunctive and Abductive Logic Programs. In Proc. ICLP-94, pp. 88\u2013100, 1994."},{"key":"1_CR32","unstructured":"B. Selman and H. J. Levesque. Abductive and Default Reasoning: A Computational Core. In Proc. AAAI-90, pp. 343\u2013348, July 1990."},{"issue":"3","key":"1_CR33","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1145\/116825.116838","volume":"38","author":"A. Gelder Van","year":"1991","unstructured":"A. Van Gelder, K. Ross, and J. Schlipf. The well-founded semantics for general logic programs. Journal of ACM, 38(3):620\u2013650, 1991.","journal-title":"Journal of ACM"}],"container-title":["Lecture Notes in Computer Science","Logic Programming and Nonmonotonic Reasoning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-59487-6_1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:47:14Z","timestamp":1742597234000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-59487-6_1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540594871","9783540492825"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/3-540-59487-6_1","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]},"assertion":[{"value":"31 May 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}