Next: Previous Work Up: Research Note: New Polynomial Previous: Preliminaries

# Our Model of Abduction

We now formalize our model; for sake of simplicity, we first define abduction problems and then the notions of hypothesis and explanation.

Definition 2 (abduction problem)   A triple is called an abduction problem if and are satisfiable propositional formulas and is a set of variables with ; is called the knowledge base of , its query and its set of abducibles.

Definition 3 (hypothesis,explanation)   Let be an abduction problem. An hypothesis for is a set of literals formed upon (seen as their conjunction), and an hypothesis for is an explanation for if is satisfiable and . If no proper subconjunction of is an explanation for , is called a best explanation for .

Note that this framework does not allow one to specify that a variable must occur unnegated (resp. negated) in an explanation. We do not think this is a prohibiting restriction, since abducibles are intuitively meant to represent the variables whose values can be, e.g., modified, observed or repaired, and then no matter their sign in an explanation. But we note that it is a restriction, and that a more general framework can be defined where the abducibles are literals and the hypotheses, conjunctions of abducibles [Mar00].

We are interested in the computational complexity of computing a best explanation for a given abduction problem, or asserting there is none at all. Following the usual model, we establish complexities with respect to the size of the representations of and and to the number of abducibles; for hardness results, the following associated decision problem is usually considered: is there at least one explanation for ? Obviously, if this latter problem is hard, then the function problem also is.

Next: Previous Work Up: Research Note: New Polynomial Previous: Preliminaries
Bruno Zanuttini 2003-06-30