Compilability of Abduction

Proceedings of the Seventeenth National Conference on Artificial Intelligence (AAAI 2000)

Abduction is one of the most important forms of reasoning and it has been successfully applied to several practical problems such as diagnosis. In this paper we investigate whether the computational complexity of abduction can be reduced by an appropriate use of preprocessing or compilation. This is motivated by the fact that part of the data of the problem (namely, the set of all possible assumptions and the theory relating assumptions and manifestations) are often known before the rest of the problem. We present a detailed analysis of the computational complexity of abduction when compilation is allowed.

 @inproceedings{libe-scha-00-c,
 title = {Compilability of Abduction},
 year = {2000},
 author = {Liberatore, Paolo and Schaerf, Marco},
 booktitle = {Proceedings of the Seventeenth National Conference on Artificial
 Intelligence (AAAI 2000)},
 }