[Back]

M. Jakl, R. Pichler, S. Woltran:
"Answer-Set Programming with Bounded Tree Width";
Talk: 21st International Joint Conference on Artificial Intelligence (IJCAI 2009), Pasadena, California, U.S.A.; 2009-07-11 - 2009-07-17; in: "Proc. of the Twenty-First Int. Joint Conference on Artificial Intelligence", C. Boutilier (ed.); AAAI Press, Menlo Park, California, U.S.A. (2009), ISBN: 978-1-57735-428-4; 816 - 822.

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. 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, even a prototypical
implementation is competitive compared to stateof-
the-art systems.

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung