We study the framework of abductive logic programming extended with integrity constraints. For this framework, we introduce a new measure of the simplicity of an explanation based on its degree of arbitrariness : the more arbitrary the explanation, the less appealing it is, with explanations having no arbitrariness — they are called constrained — being the preferred ones. In the paper, we study basic properties of constrained explanations. For the case when programs in abductive theories are stratified we establish results providing a detailed picture of the complexity of the problem to decide whether constrained explanations exist.
Abduction was introduced to artificial intelligence in early 1970s by Harry Pople Jr. , where it is now commonly understood as the @cite_3 . Over the years several criteria have been proposed to identify the preferred (best) explanations, all rooted in the Occam's razor parsimony principle. The most commonly considered one is subset-minimality @cite_2 @cite_20 @cite_6 . A more restrictive condition of minimum cardinality has also been broadly studied @cite_8 . The abduction reasoning formalism we study in the paper uses logic programs to represent background knowledge in abductive theories. It is referred to as @cite_10 @cite_15 @cite_17 . Abductive explanations which allow the removal of hypotheses are first introduced by Inoue and Sakama . The importance of abductive logic programming to knowledge representation was argued by Denecker and Schreye . It was applied in diagnosis @cite_21 , planning @cite_7 @cite_13 , natural language understanding @cite_11 , and case-based reasoning @cite_9 . Denecker and Kakas provide a comprehensive survey of the area.
@cite_13 @cite_11 @cite_7 @cite_8 @cite_9 @cite_21 @cite_6 @cite_3 @cite_2 @cite_15 @cite_10 @cite_20 @cite_17
176609766 2100657934 1801368039 1509180139
Horn clause logic programming can be extended to include abduction 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 Introduction 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 deductive 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 "knowledge 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 abduction 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 abduction and default reasoning was also pointed out in [Kowalski, 1979]. In this paper we show how abduction can be integrated with logic programming, and we concentrate on the use of abduction 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; Abduction is an important form of nonmonotonic reasoning allowing one to find explanations for certain symptoms or manifestations. When the application domain is described by a logical theory, we speak about logic-based abduction . Candidates for abductive explanations are usually subjected to minimality criteria such as subset-minimality, minimal cardinality, minimal weight, or minimality under prioritization of individual hypotheses. This paper presents a comprehensive complexity analysis of relevant decision and search problems related to abduction on propositional theories. Our results indicate that abduction is harder than deduction. In particular, we show that with the most basic forms of abduction the relevant decision problems are complete for complexity classes at the second level of the polynomial hierarchy, while the use of prioritization raises the complexity to the third level in certain cases. 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 antidexplanations 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 nonddeterministic 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 bottomdup 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. Abduction in Logic Programming started in the late 80s, early 90s, in an attempt to extend logic programming into a framework suitable for a variety of problems in Artificial Intelligence and other areas of Computer Science. This paper aims to chart out the main developments of the field over the last ten years and to take a critical view of these developments from several perspectives: logical, epistemological, computational and suitability to application. The paper attempts to expose some of the challenges and prospects for the further development of the field.