Georg Gottlob, Reinhard Pichler, Fang Wei
Abductive diagnosis is an important method for identifying possible causes which explain a given set of observations. Unfortunately, abduction suffers from the fact that most of the algorithmic problems in this area are intractable. We have recently obtained very promising results for a strongly related problem in the database area. Specifically, the PRIMALITY problem becomes efficiently solvable and highly parallelizable if the underlying functional dependencies have bounded treewidth. In the current paper, we show that these favorable results can be carried over to logic-based abduction. In fact, we even show a further generalization of these results.
Subjects: 3. Automated Reasoning; 9.2 Computational Complexity
Submitted: Apr 20, 2007