Abduction belongs to the most fundamental reasoning methods. It is a method for reverse inference, this means one is interested in explaining observed behavior by finding appropriate causes. We study logic-based abduction, where knowledge is represented by propositional formulas. The computational complexity of this problem is highly intractable in many interesting settings. In this work we therefore present an extensive parameterized complexity analysis of abduction within various fragments of propositional logic together with (combinations of) natural parameters.
|Title of host publication||Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence|
|Editors||Jorg Hoffmann, Bart Selman|
|Place of Publication||Online|
|Publisher||Association for the Advancement of Artificial Intelligence (AAAI)|
|Number of pages||7|
|Publication status||Published - 2012|
|Event||Association for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th) - Toronto, Ontario, Canada, Toronto, Canada|
Duration: 22 Jul 2012 → 26 Jul 2012
Conference number: 2012 (26th)
|Conference||Association for the Advancement of Artificial Intelligence Conference (AAAI 2012 26th)|
|Period||22/07/12 → 26/07/12|
Fellows, M., Pfandler, A., Rosamond, F., & Rummele, S. (2012). The Parameterized Complexity of Abduction. In J. Hoffmann, & B. Selman (Eds.), Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence (Vol. 1, pp. 743-749). Association for the Advancement of Artificial Intelligence (AAAI).