Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving
(funded by the Austrian Science Fund (FWF) under grant P25607)
Contents
The project has ended on June 30th, 2017.
Project team
Project leader
Project partners
Goal of the Project
Complex reasoning problems over large amounts of data arise in many of today's application domains for computer science. But handling computationally complex queries over huge data is an insurmountable obstacle for standard algorithms. The main vision of the project is to establish a new solving paradigm, which we call Decompose, Guess & Check, for solving complex reasoning problems over huge data. In particular, this paradigm will combine the strengths of Answer Set Programming (ASP) as a powerful language for declarative problem solving with the successful methodology of exploiting structure by means of tree decompositions. To this end, we will engineer a system intended as a serious competitor in the declarative solving domain. Moreover, to make the new paradigm sufficiently attractive, we show its potential in terms of applicability, and we demonstrate the usability of the method by means of case studies on a wide range of problems from diverse application areas.
TopSoftware
- D-FLAT System: Dynamic Programming Framework with Local Execution of ASP on Tree Decompositions
- D-FLAT Debugger: Debugging and Visualization Tool for D-FLAT
- D-FLAT^2 System: Variant of D-FLAT that supports efficient solving of problems that involve subset minimization
Related Webpages
- dynBDD: A system for dynamic programming on tree decompositions. Intermediate results are stored as Binary Decision Diagrams (BDDs) instead of tables (like in D-FLAT), yielding reduced memory requirements.
- Sequoia: An MSO solver that leverages small treewidth
- Hypertree Project: Project of the hypertree decomposition library used in the D-FLAT system
- SHARP Framework: A Smart Hypertree decomposition-based Algorithm fRamework for Parameterized problems. A modified version of this framework is used by the D-FLAT system. For now, D-FLAT is incompatible with the official SHARP library. If you want to compile D-FLAT, use the SHARP version provided as part of the D-FLAT source code instead, which can be found on the system page.
- Potsdam Answer Set Solving Collection: The Gringo/Clasp answer set solving tools used in the D-FLAT system
- DYNASP Project: Project about using dynamic programming on tree decompositions for solving ASP
- Autograph: A system for verifying properties on graphs of bounded clique-width via fly-automata