Equivalence in Abductive Logic

Katsumi Inoue and Chiaki Sakama

Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI-05), pages 472-477, Morgan Kaufmann Publishers, 2005.


We consider the problem of identifying equivalence of two knowledge bases which are capable of abductive reasoning. Here, a knowledge base is written in either first-order logic or nonmonotonic logic programming. In this work, we will give two definitions of abductive equivalence. The first one, explainable equivalence, requires that two abductive programs have the same explainability for any observation. Another one, explanatory equivalence, guarantees that any observation has exactly the same explanations in each abductive framework. Explanatory equivalence is a stronger notion than explainable equivalence. In first-order abduction, explainable equivalence can be verified by the notion of extensional equivalence in default theories. In nonmonotonic logic programs, explanatory equivalence can be checked by means of the notion of relative strong equivalence. We also show the complexity results for abductive equivalence.

Full Paper (gzipped postscript 52K) Slide (pdf 143K)