Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
396936 | International Journal of Approximate Reasoning | 2015 | 10 Pages |
Abstract
•Formal definition of second-best abductive solutions.•Complexity depends on the ordering: is complete for Dp or Π2Π2.•Checking solution and relevance of hypotheses.
When looking for a propositional abductive explanation of a given set of manifestations, an ordering between possible solutions is often assumed. While the complexity of computing optimal solutions is already known, in this paper we consider second-best solutions with respect to different orderings, and different definitions of what a second-best solution is: an optimal solution not already found, or a solution that is optimal among the ones not previously found.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Paolo Liberatore, Marco Schaerf,