AAAI Publications, Twenty-First International Joint Conference on Artificial Intelligence

Font Size: 
Answer-Set Programming with Bounded Treewidth
Michael Jakl, Reinhard Pichler, Stefan Woltran

Last modified: 2009-06-25

Abstract


In this paper, we present a novel approach to the evaluation of propositional answer-set programs. In particular, for programs with bounded treewidth, our algorithm is capable of (i) computing the number of answer sets in linear time and (ii) enumerating all answer sets with linear delay. Our algorithm relies on dynamic programming, which so far has not been applied to ASP-problems. Therefore, our approach significantly differs from standard ASP-systems which implement techniques stemming from SAT or CSP, and thus usually do not exploit fixed parameter properties of the programs. We provide first experimental results which underline that, for programs with low treewidth, already a prototypical implementation is competitive compared to state-of-the-art systems.

Full Text: PDF