Counting Complexity of Propositional Abduction
Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 417-421.
Abstract
Abduction is an important method of non-monotonic reasoning with many applications in AI 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 classes of theories.
@inproceedings{ijcai2007p65,
title = {Counting Complexity of Propositional Abduction},
author = {Hermann, Miki and Pichler, Reinhard},
booktitle = {Proceedings of the Twentieth International Joint Conference on
Artificial Intelligence, {IJCAI-07}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Ramon López de Mántaras},
pages = {417--421},
year = {2007},
url = {https://ijcai.org/proceedings/2007/65},
}
TY - CPAPER TI - Counting Complexity of Propositional Abduction AU - Hermann, Miki AU - Pichler, Reinhard T2 - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07 PB - International Joint Conferences on Artificial Intelligence PY - 2007 SP - 417 EP - 421 UR - https://ijcai.org/proceedings/2007/65 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
