Computing Extended Abduction Through Transaction Programs
Katsumi Inoue and Chiaki Sakama
Annals of Mathematics and Artificial Intelligence 25(3-4):339-367,
Baltzer Science Publishers, 1999.
To explain observations from nonmonotonic background theories,
one often needs removal of some hypotheses as well as addition of
other hypotheses. Moreover, some observations should not be
explained, while some are to be explained. In order to formalize
these situations, extended abduction was introduced by
Inoue and Sakama (1995) to generalize traditional abduction in the sense
that it can compute negative explanations by removing hypotheses
and anti-explanations to unexplain negative observations.
In this paper, we propose a computational mechanism for extended abduction.
When a background theory is written in a normal logic program,
we introduce its transaction program for computing extended abduction.
A transaction program is a set of non-deterministic production rules
that declaratively specify addition and deletion of abductive hypotheses.
Abductive explanations are then computed by the fixpoint of
a transaction program using a bottom-up model generation procedure.
The correctness of the proposed procedure is shown
for the class of acyclic covered abductive logic programs.
In the context of deductive databases, a transaction program provides
a declarative specification of database update.
Full Paper (gzipped postscript 240K)