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
Top
Top
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
Publications
2018
- Complexity of Secure Sets In Algorithmica, 80 (10): 2909-2940, 2018.
[ Abstract | BibTeX | doi ]
2017
- Treewidth in Non-Ground Answer Set Solving and Alliance Problems in Graphs In Technical Communications of the 33rd International Conference on Logic Programming (ICLP 2017), Volume 58 of OASICS, pages 12:1-12:12, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017.
[ Abstract | BibTeX | doi ] - Tailored tree decompositions for efficient problem solving Ph.D. Thesis, Fakultät für Informatik an der Technischen Universität Wien, 2017.
Stefan Woltran and Nysret Musliu advisors.
[ Abstract | BibTeX | pdf ] - The D-FLAT System: User Manual Technical Report DBAI-TR-2017-107, DBAI, Vienna University of Technology, 2017.
[ Abstract | BibTeX | pdf ] - htd - A Free, Open-Source Framework for (Customized) Tree Decompositions and Beyond In Proc. of the 14th International Conference on Integration of AI and OR Techniques in Constraint Programming (CPAIOR 2017), Volume 10335 of LNCS, pages 376-386, Springer, 2017.
[ Abstract | BibTeX | doi ] - Defensive Alliances in Graphs of Bounded Treewidth In CoRR, abs/1707.04251, 2017.
[ BibTeX | pdf ] - Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning In Journal of Artificial Intelligence Research, 58: 829-858, 2017.
[ Abstract | BibTeX | pdf ] - Implementing Courcelle's Theorem in a declarative framework for dynamic programming In Journal of Logic and Computation, 27 (4): 1067-1094, 2017.
[ Abstract | BibTeX | pdf ] - The Impact of Treewidth on ASP Grounding and Solving In Proc. of the 26th International Joint Conference on Artificial Intelligence (IJCAI 2017), pages 852-858, AAAI Press, 2017.
[ Abstract | BibTeX | pdf ]
2016
- htd -- A Free, Open-Source Framework for Tree Decompositions and Beyond Technical Report DBAI-TR-2016-96, DBAI, Fakultät für Informatik an der Technischen Universität Wien, 2016.
[ Abstract | BibTeX | pdf ] - lpopt: A Rule Optimization Tool for Answer Set Programming In Pre-Proc. of the 26th International Symposium on Logic-Based Program Synthesis and Transformation (LOPSTR 2016), 2016.
[ Abstract | BibTeX | pdf ] - ASP for Anytime Dynamic Programming on Tree Decompositions (Extended Abstract) In Proc. of the 39th German Conference on Artificial Intelligence (KI 2016), Volume 9904 of LNCS, pages 257-263, 2016.
[ Abstract | BibTeX | pdf ] - The Power of Non-Ground Rules in Answer Set Programming In Theory and Practice of Logic Programming, 16 (5-6): 552-569, 2016.
[ Abstract | BibTeX | doi ] - On Efficiently Enumerating Semi-Stable Extensions via Dynamic Programming on Tree Decompositions In Proc. of the 6th International Conference on Computational Models of Argument (COMMA 2016), Volume 287 of Frontiers in Artificial Intelligence and Applications, pages 107-118, IOS Press, 2016.
[ Abstract | BibTeX | doi ] - Providing Built-In Counters in a Declarative Dynamic Programming Environment In Proc. of the 39th German Conference on Artificial Intelligence (KI 2016), Volume 9904 of LNCS, pages 3-16, Springer, 2016.
[ Abstract | BibTeX | doi ] - Dynamic Programming-based QBF Solving In Proc. of the 4th International Workshop on Quantified Boolean Formulas (QBF 2016), Volume 1719 of CEUR Workshop Proceedings, pages 27-40, CEUR-WS.org, 2016.
[ Abstract | BibTeX | pdf ] - D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy In Fundamenta Informaticae, 147 (1): 27-61, 2016.
[ Abstract | BibTeX | doi ] - Shift Design with Answer Set Programming In Fundamenta Informaticae, 147 (1): 1-25, 2016.
[ Abstract | BibTeX | doi ] - ASP for Anytime Dynamic Programming on Tree Decompositions In Proc. of the 25th International Joint Conference on Artificial Intelligence (IJCAI 2016), pages 979-986, AAAI Press, 2016.
[ Abstract | BibTeX | pdf ] - Equivalence between Answer-Set Programs under (Partially) Fixed Input In Proc. of the Ninth International Symposium on Foundations of Information and Knowledge Systems (FoIKS 2016), Volume 9616 of LNCS, pages 95-111, Springer, 2016.
[ Abstract | BibTeX | pdf ] - Subset Minimization in Dynamic Programming on Tree Decompositions In AAAI-16 Workshop on Beyond NP, WS-16-05 , pages 300-306, 2016.
[ Abstract | BibTeX | pdf ] - Designing a System for the Experimental Analysis and Visualization of Dynamic Programming on Tree Decompositions Master's Thesis, Fakultät für Informatik an der Technischen Universität Wien, 2016.
Stefan Woltran and Günther Charwat advisors.
[ Abstract | BibTeX | system page ] - Complexity of Secure Sets In 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Volume 9224 of LNCS, pages 64-77, Springer, 2016.
[ Abstract | BibTeX | doi ]
2015
- Dynamic Programming on Tree Decompositions in Practice - Some Lessons Learned In 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC 2015), pages 22, IEEE Computer Society, 2015.
[ Abstract | BibTeX | doi ] - Implementing variations of the Traveling Salesperson Problem in a declarative dynamic programming environment Master's Thesis, TU Wien, 2015.
Stefan Woltran and Michael Abseher advisors.
[ BibTeX | pdf ] - Optimizing Second-Level Dynamic Programming Algorithms Master's Thesis, TU Wien, 2015.
Stefan Woltran and Bernhard Bliem advisors.
[ BibTeX | pdf ] - D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy In Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), 2015.
[ Abstract | BibTeX | pdf | system page ] - Shift Design with Answer Set Programming In Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), 2015.
[ Abstract | BibTeX | pdf ] - Efficient Problem Solving on Tree Decompositions using Binary Decision Diagrams In Proc. of the 13th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2015), Volume 9345 of LNCS, pages 213-227, Springer, 2015.
[ Abstract | BibTeX | pdf | ] - Shift-design with Answer Set Programming In Proc. of the 13th International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR 2015), Volume 9345 of LNCS, pages 32-39, Springer, 2015.
[ Abstract | BibTeX | pdf | ] - Democratix: A Declarative Approach to Winner Determination In Proc. of the 4th International Conference on Algorithmic Decision Theory (ADT 2015), Volume 9346 of LNCS, pages 253-269, Springer, 2015.
[ Abstract | BibTeX | pdf | | system page ] - D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy Technical Report DBAI-TR-2015-93, DBAI, TU Wien, 2015.
[ Abstract | BibTeX | pdf ] - Improving the Efficiency of Dynamic Programming on Tree Decompositions via Machine Learning In Proc. of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), pages 275-282, AAAI Press, 2015.
[ Abstract | BibTeX | pdf ] - Computing Secure Sets in Graphs using Answer Set Programming In Journal of Logic and Computation, 2015.
(Special issue of ASPOCP 2014)
[ Abstract | BibTeX | pdf ] - Methods for Solving Reasoning Problems in Abstract Argumentation - A Survey In Artificial Intelligence, 220 (0): 28-63, 2015.
[ Abstract | BibTeX | doi ]
2014
- Complexity of Secure Sets In CoRR, abs/1411.6549, 2014.
[ BibTeX | pdf ] - The D-FLAT System for Dynamic Programming on Tree Decompositions In Proc. of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014), Volume 8761 of LNCS, pages 558-572, Springer, 2014.
[ Abstract | BibTeX | pdf | system page ] - The D-FLAT System for Dynamic Programming on Tree Decompositions In Fourth International Workshop on Logic and Search (LaSh 2014), 2014.
[ Abstract | BibTeX | pdf | system page ] - Computing Secure Sets in Graphs using Answer Set Programming In Seventh Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2014), 2014.
[ Abstract | BibTeX | pdf ] - DEMOCRATIX: A Declarative Approach to Winner Determination In Fifth International Workshop on Computational Social Choice (COMSOC 2014), 2014.
[ Abstract | BibTeX | pdf | system page ] - D-FLAT: Progress Report Technical Report DBAI-TR-2014-86, DBAI, Vienna University of Technology, 2014.
[ Abstract | BibTeX | pdf ]
2013
- Declarative Dynamic Programming as an Alternative Realization of Courcelle's Theorem In Proc. of the Eight International Symposium on Parameterized and Exact Computation (IPEC 2013), Volume 8246 of LNCS, pages 28-40, Springer, 2013.
[ BibTeX | pdf ] - Applicability of ASP-based Problem Solving on Tree Decompositions In Third International Workshop on Graph Structures for Knowledge Representation and Reasoning (GKR 2013), 2013.
[ BibTeX | pdf ]
2012
- Decompose, Guess & Check: Declarative Problem Solving on Tree Decompositions Master's Thesis, Vienna University of Technology, 2012.
Stefan Woltran and Reinhard Pichler advisors. Received the "Distinguished Young Alumnus" award of the Faculty of Informatics at the Vienna University of Technology in June 2013.
[ BibTeX | pdf ] - D-FLAT: Declarative problem solving using tree decompositions and answer-set programming In Theory and Practice of Logic Programming, 12: 445-464, 2012.
[ Abstract | BibTeX | pdf ]
Last updated: 2017-01-09 16:22