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