The Parameterized Complexity of Abduction

Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond, Stefan Rümmele

AAAI 2012 pp. 743-749

doi:10.1609/AAAI.V26I1.8224 /aaai/2012/fellows2012aaai-parameterized/

Abstract

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.

PDF AAAI Semantic Scholar

Cite

Text

Fellows et al. "The Parameterized Complexity of Abduction." AAAI Conference on Artificial Intelligence, 2012. doi:10.1609/AAAI.V26I1.8224

Markdown

[Fellows et al. "The Parameterized Complexity of Abduction." AAAI Conference on Artificial Intelligence, 2012.](https://mlanthology.org/aaai/2012/fellows2012aaai-parameterized/) doi:10.1609/AAAI.V26I1.8224

BibTeX

@inproceedings{fellows2012aaai-parameterized,
  title     = {{The Parameterized Complexity of Abduction}},
  author    = {Fellows, Michael R. and Pfandler, Andreas and Rosamond, Frances A. and Rümmele, Stefan},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2012},
  pages     = {743-749},
  doi       = {10.1609/AAAI.V26I1.8224},
  url       = {https://mlanthology.org/aaai/2012/fellows2012aaai-parameterized/}
}