{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,17]],"date-time":"2025-04-17T14:48:48Z","timestamp":1744901328746},"reference-count":30,"publisher":"Cambridge University Press (CUP)","issue":"4-5","license":[{"start":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T00:00:00Z","timestamp":1346803200000},"content-version":"unspecified","delay-in-days":66,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory and Practice of Logic Programming"],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1017\/s1471068412000129","type":"journal-article","created":{"date-parts":[[2012,9,5]],"date-time":"2012-09-05T11:28:45Z","timestamp":1346844525000},"page":"445-464","source":"Crossref","is-referenced-by-count":6,"title":["D-FLAT: Declarative problem solving using tree decompositions and answer-set programming"],"prefix":"10.1017","volume":"12","author":[{"given":"BERNHARD","family":"BLIEM","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHAEL","family":"MORAK","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"STEFAN","family":"WOLTRAN","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2012,9,5]]},"reference":[{"key":"S1471068412000129_ref11","unstructured":"Gebser M. , Kaminski R. , Kaufmann B. , Ostrowski M. , Schaub T. and Thiele S. 2010. A user's guide to gringo, clasp, clingo, and iclingo. Preliminary Draft. Available under http:\/\/potassco.sourceforge.net."},{"key":"S1471068412000129_ref16","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"S1471068412000129_ref30","unstructured":"Zhou N.-F. 2011. The language features and architecture of B-Prolog. CoRR abs\/1103.0812."},{"key":"S1471068412000129_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2009.06.002"},{"key":"S1471068412000129_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-60085-2_17"},{"key":"S1471068412000129_ref20","first-page":"816","volume-title":"Proceedings of IJCAI'09","author":"Jakl","year":"2009"},{"key":"S1471068412000129_ref28","first-page":"42","article-title":"Dynamic programming","volume":"5","author":"Wagner","year":"1995","journal-title":"The Mathematica Journal"},{"key":"S1471068412000129_ref19","doi-asserted-by":"publisher","DOI":"10.1002\/spe.824"},{"key":"S1471068412000129_ref29","doi-asserted-by":"crossref","unstructured":"Xu J. , Jiao F. and Berger B. 2005. A tree-decomposition approach to protein structure prediction. In Proceedings of CSB 2005. 247\u2013256.","DOI":"10.1109\/CSB.2005.9"},{"key":"S1471068412000129_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/BF03037169"},{"key":"S1471068412000129_ref22","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.1967.1098755"},{"key":"S1471068412000129_ref21","doi-asserted-by":"publisher","DOI":"10.1002\/net.10046"},{"key":"S1471068412000129_ref18","first-page":"236","volume-title":"Proceedings of CP 2010","author":"Greco","year":"2010"},{"key":"S1471068412000129_ref7","first-page":"193","volume-title":"Handbook of Theoretical Computer Science, Volume B: Formal Models and Sematics (B)","author":"Courcelle","year":"1990"},{"key":"S1471068412000129_ref15","first-page":"16","volume-title":"Proceedings of ICALP (2)","author":"Gottlob","year":"2009"},{"key":"S1471068412000129_ref23","doi-asserted-by":"publisher","DOI":"10.1145\/1149114.1149117"},{"key":"S1471068412000129_ref4","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2009.03.008"},{"key":"S1471068412000129_ref3","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"S1471068412000129_ref25","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018930122475"},{"key":"S1471068412000129_ref6","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm035"},{"key":"S1471068412000129_ref1","first-page":"1","article-title":"A tourist guide through treewidth","volume":"11","author":"Bodlaender","year":"1993","journal-title":"Acta Cybernetica"},{"key":"S1471068412000129_ref2","first-page":"1","volume-title":"Proceedings of SOFSEM","author":"Bodlaender","year":"2005"},{"key":"S1471068412000129_ref8","first-page":"1","volume-title":"Proceedings of MICAI","author":"Dermaku","year":"2008"},{"key":"S1471068412000129_ref9","doi-asserted-by":"crossref","unstructured":"Eisner J. and Filardo N. W. 2011. Dyna: Extending datalog for modern AI (full version). Available under http:\/\/cs.jhu.edu\/~jason\/papers\/eisner+filardo.datalog11-long.pdf.","DOI":"10.1007\/978-3-642-24206-9_11"},{"key":"S1471068412000129_ref26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"S1471068412000129_ref17","doi-asserted-by":"publisher","DOI":"10.1145\/1838552.1838555"},{"key":"S1471068412000129_ref5","doi-asserted-by":"publisher","DOI":"10.1145\/2043174.2043195"},{"key":"S1471068412000129_ref12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.3233\/AIC-2011-0491","article-title":"Potassco: The potsdam answer set solving collection","volume":"24","author":"Gebser","year":"2011","journal-title":"AI Communications"},{"key":"S1471068412000129_ref10","first-page":"54","volume-title":"Proceedings of LPNMR","author":"Gebser","year":"2011"},{"key":"S1471068412000129_ref13","doi-asserted-by":"crossref","first-page":"195","DOI":"10.3233\/AIC-2011-0496","article-title":"An incremental answer set programming based system for finite model computation","volume":"24","author":"Gebser","year":"2011","journal-title":"AI Communications"}],"container-title":["Theory and Practice of Logic Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S1471068412000129","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,13]],"date-time":"2020-07-13T06:33:16Z","timestamp":1594621996000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S1471068412000129\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":30,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["S1471068412000129"],"URL":"https:\/\/doi.org\/10.1017\/s1471068412000129","relation":{},"ISSN":["1471-0684","1475-3081"],"issn-type":[{"value":"1471-0684","type":"print"},{"value":"1475-3081","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}