[Back]

M Herman, R. Pichler:
"Counting Complexity of Minimal Cardinality and Minimal Weight Abduction";
Talk: 11^th European Conference (JELIA 2008), Dresden, Deutschland; 09-28-2008 - 10-01-2008; in: "Logics in Artificial Intelligence", S. Hölldobler, C. Lutz, H. Wansing (ed.); LNAI 5293 (2008), ISBN: 3-540-87802-5; 206 - 218.

Abduction is an important method of non-monotonic reasoning with many applications in artificial intelligence and related topics. In this paper, we concentrate on propositional abduction, where die background knowledge is given by a propositional formula. We have recently started to study the counting complexity of propositional abduction. However, several important cases have been left open, namely, the cases when we restrict ourselves to solutions with minimal cardinality or with minimal weight. These cases - possibly combined with priorities - are now settled in this paper. We thus arrive at a complete picture of the counting complexity of propositional abduction.