Efficient Datalog Abduction through Bounded Treewidth

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

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.