[Zurück]

B. Bliem, R. Pichler, S. Woltran:
"Implementing Courcelle's Theorem in a declarative framework for dynamic programming";
Journal of Logic and Computation, 27 (2017), 4; S. 1067 - 1094.

Many computationally hard problems become tractable if the graph structure underlying the problem instance exhibits small treewidth. A recent approach to put this idea into practice is based on a declarative interface to Answer Set Programming that allows us to specify dynamic programming over tree decompositions in this language, delegating the computation to dedicated solvers. In this article, we prove that this method can be applied to any problem whose fixed-parameter tractability follows from Courcelle's Theorem.

Implementing; Courcelle's; Theorem; declarative; framework;dynamic;programming;

http://dx.doi.org/10.1093/logcom/exv089

Projektleitung Reinhard Pichler:
Effiziente, parametrisierte Algorithmen in Künstlicher Intelligenz und logischem Schließen

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