[Zurück]


Vorträge und Posterpräsentationen (mit Tagungsband-Eintrag):

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



Kurzfassung englisch:
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.


Zugeordnete Projekte:
Projektleitung Stefan Woltran:
Answer-Set Programming Erweiterungen für Problemlösungen auf Zerlegungen

Projektleitung Stefan Woltran:
START


Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.