[Back]

J. Fichte, M. Hecher, M. Morak, S. Woltran:
"Answer Set Solving using Tree Decompositions and Dynamic Programming -- The DynASP2 System";
Report No. DBAI-TR-2016-101, 2016; 70 pages.

In this paper, we present novel algorithms for propositional answer set programming (ASP). In particular, we employ dynamic programming on tree decompositions which leads to algorithms that directly exploit the structure of the given ASP program. It is well-known that for tree-like ASP programs (that is, those programs whose treewidth is bounded), the complexity of solving drops from the second level of the polynomial hierarchy to polynomial time. Based on the idea of a dynamic programming algorithm previously introduced by Jakl, Pichler, and Woltran at IJCAI 2009, we propose several graph representations for ASP programs amenable for tree decomposition-based algorithms, and we present multiple ASP solving algorithms for these that can handle the full, state-of-the-art lparse ASP syntax that is used by most of the currently available ASP solvers. Finally, we present two prototype systems with these algorithms, using advanced implementation techniques. We show that these implementations exhibit favorable runtime behaviour especially for the problem of answer set counting.

Project Head Stefan Woltran:
START