[Back]


Talks and Poster Presentations (with Proceedings-Entry):

B. Bliem, G. Charwat, M. Hecher, S. Woltran:
"D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy";
Talk: 8th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2015, Cork, Ireland; 08-31-2015; in: "8th Workshop on Answer Set Programming and Other Computing Paradigms, ASPOCP 2015", D. Inclezan, M. Maratea (ed.); (2015), 15 pages.



English abstract:
Many problems from the area of AI have been shown tractable for bounded treewidth. In order to put such results into practice, quite involved dynamic programming (DP) algorithms on tree decompositions have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset-minimization. In this paper we present D-FLAT^2, a system that allows one to obtain DP algorithms (specified in ASP) from simpler principles, where the DP formalization of subset-minimization is performed automatically.

We illustrate the method at work by providing several DP algorithms - given in form of ASP programs - that are more space-efficient than existing solutions, while featuring improved readability, reuse and therefore maintainability of ASP code. Experiments show that our approach also yields a significant improvement in runtime performance.


Related Projects:
Project Head Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Project Head Stefan Woltran:
START


Created from the Publication Database of the Vienna University of Technology.