Abduction Compared with Negation by Failure.
Kave Eshghi, Robert Kowalski · International Conference on Lightning Protection · 1989
Horn clause logic programming can be extended to include with integrity constraints. In the resulting extension of logic programming, negation by failure can be simulated by making negative conditions abducible and by imposing appropriate denials and disjunctions as integrity constraints. This gives an alternative semantics for negation by failure, which generalises the stable model semantics of negation by failure. The abductive extension of logic programming extends negation by failure in three ways: (1) computation can be perfonned in alternative minimal models, (2) positive as well as negative conditions can be made abducible, and (3) other integrity constraints can also be accommodated. * This paper was written while the first author was at Imperial College. 235 The tenn abduction was introduced by the philosopher Charles Peirce [1931] to refer to a particular kind of hypothetical reasoning. In the simplest case, it has the fonn: From A and A fB infer B as a possible explanation of A. Abduction has been given prominence in Charniak and McDennot's [1985] Introduction to Artificial Intelligence, where it has been applied to expert systems and story comprehension. Independently, several authors have developed techniques to drive the generation of abductive hypotheses. Cox and Pietrzykowski [1986] construct hypotheses from the dead ends of linear resolution proofs. Finger and Genesereth [1985] generate deductive solutions to design problems using the residue left behind in resolution proofs. Poole, Goebel and Aleliunas [1987] also use linear resolution to generate hypotheses. All impose the restriction that hypotheses should be consistent with the base. Abduction is a fonn of non-monotonic reasoning, because hypotheses which are consistent with one state of a knowledge base may become inconSistent when new knowledge is added. Poole [1988] argues that is preferable to noh-monotonic logics for default reasoning. In this view, defaults are hypotheses fonnulated within classical logic rather than conclusions derived withln some fonn of non-monotonic logic. The similarity between and default reasoning was also pointed out in [Kowalski, 1979]. In this paper we show how can be integrated with logic programming, and we concentrate on the use of to generalise negation by failure. Conditional Answers Compared with Abduction In the simplest case, a logic program consists of a set of Horn Clauses, which are used backward to_reduce goals to sub goals. The initial goal is solved when there are no subgollls left;