×

D-FLAT: declarative problem solving using tree decompositions and answer-set programming. (English) Zbl 1260.68057

Summary: In this work, we propose answer-set programming (ASP) as a tool for rapid prototyping of dynamic programming algorithms based on tree decompositions. In fact, many such algorithms have been designed, but only a few of them found their way into implementation. The main obstacle is the lack of easy-to-use systems which (i) take care of building a tree decomposition and (ii) provide an interface for declarative specifications of dynamic programming algorithms.
In this paper, we present D-FLAT, a novel tool that relieves the user of having to handle all the technical details concerned with parsing, tree decomposition, the handling of data structures, etc. Instead, it is only the dynamic programming algorithm itself which has to be specified in the ASP language. D-FLAT employs an ASP solver in order to compute the local solutions in the dynamic programming algorithm.
In the paper, we give a few examples illustrating the use of D-FLAT and describe the main features of the system. Moreover, we report experiments which show that ASP-based D-FLAT encodings for some problems outperform monolithic ASP encodings on instances of small treewidth.

MSC:

68N17 Logic programming
90C39 Dynamic programming

Software:

oClingo; D-FLAT
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Greco, Proceedings of CP 2010 pp 236– (2010)
[2] Jakl, Proceedings of IJCAI’09 pp 816– (2009)
[3] DOI: 10.1006/jcss.2001.1809 · Zbl 1052.68025 · doi:10.1006/jcss.2001.1809
[4] Gottlob, Proceedings of ICALP (2) pp 16– (2009)
[5] DOI: 10.1007/BF03037169 · doi:10.1007/BF03037169
[6] Dermaku, Proceedings of MICAI pp 1– (2008)
[7] Gebser, AI Communications 24 pp 195– (2011)
[8] Courcelle, Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B) pp 193– (1990)
[9] Gebser, AI Communications 24 pp 107– (2011)
[10] DOI: 10.1093/comjnl/bxm035 · Zbl 05534221 · doi:10.1093/comjnl/bxm035
[11] DOI: 10.1145/2043174.2043195 · doi:10.1145/2043174.2043195
[12] Gebser, Proceedings of LPNMR pp 54– (2011)
[13] DOI: 10.1016/j.ic.2009.03.008 · Zbl 1186.68328 · doi:10.1016/j.ic.2009.03.008
[14] DOI: 10.1093/comjnl/bxm037 · Zbl 05534220 · doi:10.1093/comjnl/bxm037
[15] Bodlaender, Proceedings of SOFSEM pp 1– (2005)
[16] Bodlaender, Acta Cybernetica 11 pp 1– (1993)
[17] Wagner, The Mathematica Journal 5 pp 42– (1995)
[18] DOI: 10.1016/j.jda.2009.06.002 · Zbl 1214.05166 · doi:10.1016/j.jda.2009.06.002
[19] DOI: 10.1016/0095-8956(84)90013-3 · Zbl 0548.05025 · doi:10.1016/0095-8956(84)90013-3
[20] DOI: 10.1023/A:1018930122475 · Zbl 0940.68018 · doi:10.1023/A:1018930122475
[21] Marek, The Logic Programming Paradigm – A 25-Year Perspective pp 375– (1999) · doi:10.1007/978-3-642-60085-2_17
[22] DOI: 10.1145/1149114.1149117 · Zbl 1367.68308 · doi:10.1145/1149114.1149117
[23] DOI: 10.1109/TAC.1967.1098755 · doi:10.1109/TAC.1967.1098755
[24] DOI: 10.1002/net.10046 · Zbl 1027.90072 · doi:10.1002/net.10046
[25] DOI: 10.1002/spe.824 · Zbl 05278557 · doi:10.1002/spe.824
[26] DOI: 10.1145/1838552.1838555 · Zbl 1351.68110 · doi:10.1145/1838552.1838555
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.