2006 · 31 citations · 17 references
ComputingComputer ScienceAlgorithmsArtificial IntelligenceKnowledge RepresentationAutomated ReasoningDeductive ReasoningLogic ProgrammingAbductive Logic ProgrammingComplexityComplexity Of SatisfiabilityHierarchyPolynomial HierarchyWorst-case Complexity
<p>Several forms of reasoning in AI – like abduction, closed world reasoning, circumscription, and disjunctive logic programming – are well known to be intractable. In fact, many of the relevant problems are on the second or third level of the polynomial hierarchy. In this paper, we show how the notion of treewidth can be fruitfully applied to this area. In particular, we show that all these problems become tractable (actually, even solvable in linear time), if the treewidth of the involved formulae or programs is bounded by some constant.</p> <p>Clearly, these theoretical tractability results as such do not immediately yield feasible algorithms. However, we have recently established a new method based on monadic datalog which allowed us to design an efficient algorithm for a related problem in the database area. In this work, we exploit the monadic datalog approach to construct new algorithms for logic-based abduction.</p>
17
The stable model semantics for logic programming
Michael Gelfond, Vladimir Lifschitz · 1988 · 3.4K citations
Michael R. Fellows · Electronic Notes in Theoretical Computer Science · 2002 · 2.9K citations · Full text
Easy problems for tree-decomposable graphs
Stefan Arnborg, Jens Lagergren, Detlef Seese · Journal of Algorithms · 1991 · 874 citations
The complexity of logic-based abduction
Thomas Eiter, Georg Gottlob · Journal of the ACM · 1995 · 428 citations · Full text