{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T06:48:28Z","timestamp":1725518908944},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540878025"},{"type":"electronic","value":"9783540878032"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-87803-2_18","type":"book-chapter","created":{"date-parts":[[2008,9,23]],"date-time":"2008-09-23T10:35:16Z","timestamp":1222166116000},"page":"206-218","source":"Crossref","is-referenced-by-count":1,"title":["Counting Complexity of Minimal Cardinality and Minimal Weight Abduction"],"prefix":"10.1007","author":[{"given":"Miki","family":"Hermann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Reinhard","family":"Pichler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"3","key":"18_CR1","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1016\/j.tcs.2005.03.012","volume":"340","author":"A. Durand","year":"2005","unstructured":"Durand, A., Hermann, M., Kolaitis, P.G.: Subtractive reductions and complete problems for counting complexity classes. Theoretical Computer Science\u00a0340(3), 496\u2013513 (2005)","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"18_CR2","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/200836.200838","volume":"42","author":"T. Eiter","year":"1995","unstructured":"Eiter, T., Gottlob, G.: The complexity of logic-based abduction. Journal of the Association for Computing Machinery\u00a042(1), 3\u201342 (1995)","journal-title":"Journal of the Association for Computing Machinery"},{"key":"18_CR3","first-page":"62","volume-title":"Proc. 18th AAAI","author":"T. Eiter","year":"2002","unstructured":"Eiter, T., Makino, K.: On computing all abductive explanations. In: Proc. 18th AAAI, Edmonton, Alberta, Canada, pp. 62\u201367. AAAI Press, Menlo Park (2002)"},{"key":"18_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/978-3-540-45220-1_18","volume-title":"Computer Science Logic","author":"T. Eiter","year":"2003","unstructured":"Eiter, T., Makino, K.: Generating all abductive explanations for queries on propositional Horn theories. In: Baaz, M., Makowsky, J.A. (eds.) CSL 2003. LNCS, vol.\u00a02803, pp. 197\u2013211. Springer, Heidelberg (2003)"},{"key":"18_CR5","first-page":"352","volume-title":"Proc. 2nd PODS","author":"R. Fagin","year":"1983","unstructured":"Fagin, R., Ullman, J.D., Vardi, M.Y.: On the semantics of updates in databases. In: Proc. 2nd PODS, Atlanta, Georgia, USA, pp. 352\u2013365. ACM Press, New York (1983)"},{"key":"18_CR6","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W.H. Freeman and Co., New York (1979)"},{"issue":"6","key":"18_CR7","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/BF01204168","volume":"28","author":"W.I. Gasarch","year":"1995","unstructured":"Gasarch, W.I., Krentel, M.W., Rappoport, K.J.: OptP as the normal behavior of NP-complete problems. Mathematical Systems Theory\u00a028(6), 487\u2013514 (1995)","journal-title":"Mathematical Systems Theory"},{"issue":"1","key":"18_CR8","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1145\/203610.203611","volume":"26","author":"L.A. Hemaspaandra","year":"1995","unstructured":"Hemaspaandra, L.A., Vollmer, H.: The satanic notations: Counting classes beyond #P and other definitional adventures. SIGACT News\u00a026(1), 2\u201313 (1995)","journal-title":"SIGACT News"},{"key":"18_CR9","first-page":"417","volume-title":"Proc. 20th IJCAI 2007","author":"M. Hermann","year":"2007","unstructured":"Hermann, M., Pichler, R.: Counting complexity of propositional abduction. In: Veloso, M.M. (ed.) Proc. 20th IJCAI 2007, Hyderabad, India, pp. 417\u2013422. AAAI Press, Menlo Park (2007)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-540-69733-6_16","volume-title":"Computing and Combinatorics","author":"M. Hermann","year":"2008","unstructured":"Hermann, M., Pichler, R.: Complexity of counting the optimal solutions. In: Hu, X., Wang, J. (eds.) COCOON 2008. LNCS, vol.\u00a05092, pp. 149\u2013159. Springer, Heidelberg (2008)"},{"key":"18_CR11","first-page":"119","volume-title":"Proc. 17th IJCAI 2001","author":"A. Herzig","year":"2001","unstructured":"Herzig, A., Lang, J., Marquis, P., Polacsek, T.: Updates, actions, and planning. In: Nebel, B. (ed.) Proc. 17th IJCAI 2001, Seattle, Washington, USA, pp. 119\u2013124. Morgan Kaufmann, San Francisco (2001)"},{"key":"18_CR12","first-page":"650","volume-title":"Proc. 16th VLDB","author":"A.C. Kakas","year":"1990","unstructured":"Kakas, A.C., Mancarella, P.: Database updates through abduction. In: McLeod, D., Sacks-Davis, R., Schek, H.-J. (eds.) Proc. 16th VLDB, Brisbane, Queensland, Australia, pp. 650\u2013661. Morgan Kaufmann, San Francisco (1990)"},{"key":"18_CR13","first-page":"138","volume-title":"Counting problems and #P","author":"D.C. Kozen","year":"1992","unstructured":"Kozen, D.C.: The design and analysis of algorithms. In: Counting problems and #P, ch.\u00a026, pp. 138\u2013143. Springer, Heidelberg (1992)"},{"issue":"3","key":"18_CR14","doi-asserted-by":"publisher","first-page":"490","DOI":"10.1016\/0022-0000(88)90039-6","volume":"36","author":"M.W. Krentel","year":"1988","unstructured":"Krentel, M.W.: The complexity of optimization problems. Journal of Computer and System Sciences\u00a036(3), 490\u2013509 (1988)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"18_CR15","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0304-3975(92)90073-O","volume":"97","author":"M.W. Krentel","year":"1992","unstructured":"Krentel, M.W.: Generalizations of OptP to the polynomial hierarchy. Theoretical Computer Science\u00a097(2), 183\u2013198 (1992)","journal-title":"Theoretical Computer Science"},{"key":"18_CR16","series-title":"Lecture Notes in Artificial Intelligence","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/11546207_33","volume-title":"Logic Programming and Nonmonotonic Reasoning","author":"I. Papatheodorou","year":"2005","unstructured":"Papatheodorou, I., Kakas, A.C., Sergot, M.J.: Inference of gene relations from microarray data by abduction. In: Baral, C., Greco, G., Leone, N., Terracina, G. (eds.) LPNMR 2005. LNCS (LNAI), vol.\u00a03662, pp. 389\u2013393. Springer, Heidelberg (2005)"},{"key":"18_CR17","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4419-8682-5","volume-title":"Abductive inference models for diagnostic problem solving","author":"Y. Peng","year":"1990","unstructured":"Peng, Y., Reggia, J.A.: Abductive inference models for diagnostic problem solving. Springer, Heidelberg (1990)"},{"issue":"1","key":"18_CR18","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0004-3702(93)90061-F","volume":"64","author":"D. Poole","year":"1993","unstructured":"Poole, D.: Probabilistic Horn abduction and bayesian networks. Artificial Intelligence\u00a064(1), 81\u2013129 (1993)","journal-title":"Artificial Intelligence"},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of computing the permanent. Theoretical Computer Science\u00a08(2), 189\u2013201 (1979)","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"18_CR20","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM Journal on Computing\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Logics in Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-87803-2_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T11:49:55Z","timestamp":1619524195000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-87803-2_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540878025","9783540878032"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-87803-2_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[]}}