Next: Acknowledgments Up: Research Note: New Polynomial Previous: DNFs

# Discussion and Perspectives

The general algorithm presented in this note allows us to derive new polynomial restrictions of abduction problems; even if this is not discussed here, for lack of space, it also allows to unify some previously known such restrictions (such as in CNF and in DNF, or in monotone CNF and given as a clause). The following list summarizes the main new polynomial restrictions:

• given as an affine formula and as a disjunction of linear equations (Proposition 2)
• in Horn-renamable DNF and given as a clause (Proposition 4)
• in DNF and given as a clause (Proposition 4)
• in Horn (reverse Horn) DNF and in positive (negative) CNF (Proposition 5)
• in negative (positive) DNF and in reverse Horn (Horn) CNF (Proposition 5).
Moreover, even if there is no guarantee for efficiency in the general case the presentation of our algorithm does not depend on the syntactic form of or , and it uses only standard operations on Boolean functions (projection, conjunction, negation).

Another interesting feature of this algorithm is that before minimization it computes the explanations intentionnally. Consequently, all the full explanations can be enumerated with roughly the same delay as the models of the formula representing them (). However, of course, there is no guarantee that two of them would not be minimized into the same best explanation, which prevents from concluding that our algorithm can enumerate all the best explanations; trying to extend it into this direction would be an interesting problem. For more details about enumeration we refer the reader to Eiter and Makino's work [EM02].

As identified by Selman and Levesque [SL90], central to the task is the notion of projection over a set of variables, and our algorithm isolates this subtask. However, our notion of projection only concerns variables, and not literals, which prevents from imposing a sign to the literals the hypotheses are formed upon, contrariwise to more general formalizations proposed for abduction, as Marquis' [Mar00]. Even if we think this is not a prohibiting restriction, it would be interesting to try to fix that weakness of our algorithm while preserving its polynomial classes.

Another problem of interest is the behaviour of our algorithm when and are not only propositional formulas, but more generally multivalued theories, in which the domain of variables is not restricted to be : e.g., signed formulas [BHM99]. This framework is used, for instance, for configuration problems by Amilhastre et al. [AFM02]. It is easily seen that our algorithm is still correct in this framework; however, there is still left to study in which cases its running time is polynomial.

Finally, problems of great interest are those of deciding the relevance or the necessity of an abducible [EG95]. An abducible is said to be relevant to an abduction problem if there is at least one best explanation for containing or , and necessary to if all the best explanations for contain or . It is easily seen that is necessary for if and only if has no explanation, hence showing that polynomial restrictions for the search for explanations are polynomial as well for deciding the necessity of an hypothesis as soon as they are stable under the substitution of for , which is the case for all restrictions considered in this note. Contrastingly, we do not know of any such relation for relevance, and the study of this problem would also be of great interest.

Next: Acknowledgments Up: Research Note: New Polynomial Previous: DNFs
Bruno Zanuttini 2003-06-30