ML Anthology

Counting Complexity of Propositional Abduction

Miki Hermann, Reinhard Pichler
IJCAI 2007 pp. 417-422
doi:10.1016/j.jcss.2009.12.001 /ijcai/2007/hermann2007ijcai-counting/

Abstract

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 the background knowledge is given by a propositional formula. Decision problems of great interest are the existence and the relevance problems. The complexity of these decision problems has been systematically studied while the counting complexity of propositional abduction has remained obscure. The goal of this work is to provide a comprehensive analysis of the counting complexity of propositional abduction in various settings.

PDF Semantic Scholar

Cite

Text

Hermann and Pichler. "Counting Complexity of Propositional Abduction." International Joint Conference on Artificial Intelligence, 2007. doi:10.1016/j.jcss.2009.12.001

Markdown

[Hermann and Pichler. "Counting Complexity of Propositional Abduction." International Joint Conference on Artificial Intelligence, 2007.](https://mlanthology.org/ijcai/2007/hermann2007ijcai-counting/) doi:10.1016/j.jcss.2009.12.001

BibTeX

@inproceedings{hermann2007ijcai-counting,
  title     = {{Counting Complexity of Propositional Abduction}},
  author    = {Hermann, Miki and Pichler, Reinhard},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2007},
  pages     = {417-422},
  doi       = {10.1016/j.jcss.2009.12.001},
  url       = {https://mlanthology.org/ijcai/2007/hermann2007ijcai-counting/}
}