Specifying Transactions for Extended Abduction

Katsumi Inoue and Chiaki Sakama

Proceedings of the 6th International Conference on Principles of Knowledge Representation and Reasoning (KR'98), pages 394-405, Morgan Kaufmann, 1998.


Extended abduction introduced by Inoue and Sakama (1995) generalizes traditional abduction in the sense that it can compute negative explanations by removing hypotheses from a nonmonotonic background theory, rather than only adding them. Also, it has a mechanism of computing anti-explanations to unexplain negative observations. Such extended abduction not only enhances reasoning ability of traditional abduction but has useful applications to nonmonotonic theory change. In this paper, we study the computational aspect of extended abduction. Given a background theory written in nonmonotonic logic programming, we introduce its transaction program for computing extended abduction. A transaction program is a set of non-deterministic production rules that specify addition and deletion of abductive hypotheses. Abductive explanations are computed by the fixpoint of a transaction program using a bottom-up model generation procedure. In the context of databases, a transaction program provides a declarative specification of database update.

Full Paper (gzipped postscript 90K)