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

Abstract

Abductive diagnosis is an important method to iden-tify explanations for a given set of observations. Un-fortunately, most of the algorithmic problems in this area are intractable. We have recently shown (Gott-lob, Pichler, & Wei 2006) that these problems become tractable if the underlying clausal theory has bounded treewidth. However, turning these theoretical tractabil-ity results into practically efficient algorithms turned out to be very problematical. In (Gottlob, Pichler, & Wei 2007), we have established a new method based on monadic datalog which remedies this unsatisfactory sit-uation. 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.