Abduction with Bounded Treewidth: From Theoretical Tractability to Practically Efficient Computation

Georg Gottlob, Reinhard Pichler, Fang Wei

Abductive diagnosis is an important method to identify explanations for a given set of observations. Unfortunately, most of the algorithmic problems in this area are intractable. We have recently shown that these problems become tractable if the underlying clausal theory has bounded treewidth. However, turning these theoretical tractability results into practically efficient algorithms turned out to be very problematical. In (Gottlog, Pichler, Wei 2007), we have established a new method based on monadic datalog which remedies this unsatisfactory situation. Specifically, we designed an efficient algorithm for a strongly related problem in the database area. In the current paper, we show that these favorable results can be carried over to logic-based abduction.

Subjects: 9.2 Computational Complexity; 1.7 Expert Systems

Submitted: Apr 14, 2008

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.