Answer-Set Programming with Bounded Treewidth

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. Michael Jakl, Reinhard Pichler, Stefan Woltran