D-FLAT: declarative problem solving using tree decompositions and answer-set programming

DOI10.1017/S1471068412000129MaRDI QIDQ4911127zbMATH OpenFDO

Authors Bernhard Bliem, Michael Morak, Stefan Woltran

Publication date 13 March 2013

Published in Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.1931

zbMATH Keywords

D-FLAT encodingdynamic programming algorithms

Mathematics Subject Classification ID

Logic programming (68N17) Dynamic programming (90C39)

Abstract: 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.

Recommendations

• D-FLAT^2: subset minimization in dynamic programming on tree decompositions made easy
• The D-FLAT system for dynamic programming on tree decompositions
• DynASP2.5: Dynamic Programming on Tree Decompositions in Action
• A dynamic-programming based ASP-solver
• Implementing Courcelle's theorem in a declarative framework for dynamic programming

Cites work

• Algorithms for propositional model counting
• Graph minors. III. Planar tree-width
• Hypertree decompositions and tractable queries
• Logic programs with stable model semantics as a constraint programming paradigm
• Monadic Datalog over finite structures of bounded treewidth
• Solving partial constraint satisfaction problems with tree decomposition
• The DLV system for knowledge representation and reasoning
• Treewidth computations. I: Upper bounds

Cited in

(7)

• Methods for solving reasoning problems in abstract argumentation -- a survey
• The D-FLAT system for dynamic programming on tree decompositions
• Efficient problem solving on tree decompositions using binary decision diagrams
• D-FLAT^2: subset minimization in dynamic programming on tree decompositions made easy
• A dynamic-programming based ASP-solver
• Redundant Sudoku rules
• ICCMA 2023: 5th international competition on computational models of argumentation

Describes a project that uses

Uses Software

• D-FLAT
• oClingo

This page was built for publication: D-FLAT: declarative problem solving using tree decompositions and answer-set programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4911127)