Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > D-FLAT Project

Tools: Print


Extending the Answer-Set Programming Paradigm to Decomposed Problem Solving

(funded by the Austrian Science Fund (FWF) under grant P25607)


Contents


News for this project are collected in our news archive.

Project team

Project leader

Project staff

Project partners

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.

Top

Software

  • 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
Top

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
Top

Publications

2017

  1. Bernhard Bliem, Reinhard Pichler and Stefan Woltran Implementing Courcelle's Theorem in a declarative framework for dynamic programming In Journal of Logic and Computation, 2017.
    Early access available, to appear.
    [ Abstract | BibTeX | doi  ]

2016

  1. Manuel Bichler, Michael Morak and Stefan Woltran 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  ]
  2. Bernhard Bliem, Benjamin Kaufmann, Torsten Schaub and Stefan Woltran 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  ]
  3. Manuel Bichler, Michael Morak and Stefan Woltran 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  ]
  4. Bernhard Bliem, Markus Hecher and Stefan Woltran 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  ]
  5. Michael Abseher, Marius Moldovan and Stefan Woltran 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  ]
  6. Günther Charwat and Stefan Woltran 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  ]
  7. Bernhard Bliem, Günther Charwat, Markus Hecher and Stefan Woltran D-FLAT^2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy In Fundamenta Informaticae, 147 (1): 27-61, 2016.
    [ Abstract | BibTeX | doi  ]
  8. Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub and Stefan Woltran Shift Design with Answer Set Programming In Fundamenta Informaticae, 147 (1): 1-25, 2016.
    [ Abstract | BibTeX | doi  ]
  9. Bernhard Bliem, Benjamin Kaufmann, Torsten Schaub and Stefan Woltran 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  ]
  10. Bernhard Bliem and Stefan Woltran 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  ]
  11. Bernhard Bliem, Günther Charwat, Markus Hecher and Stefan Woltran 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  ]
  12. Thomas Ambroz and Andreas Jusits 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  ]
  13. Bernhard Bliem and Stefan Woltran 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

  1. Stefan Woltran 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  ]
  2. Marius Moldovan 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  ]
  3. Markus Hecher Optimizing Second-Level Dynamic Programming Algorithms Master's Thesis, TU Wien, 2015.
    Stefan Woltran and Bernhard Bliem advisors.
    [ BibTeX | pdf  ]
  4. Bernhard Bliem, Günther Charwat, Markus Hecher and Stefan Woltran 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  ]
  5. Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub and Stefan Woltran Shift Design with Answer Set Programming In Eighth Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2015), 2015.
    [ Abstract | BibTeX | pdf  ]
  6. Günther Charwat and Stefan Woltran 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  | slides  ]
  7. Michael Abseher, Martin Gebser, Nysret Musliu, Torsten Schaub and Stefan Woltran 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  | slides  ]
  8. Günther Charwat and Andreas Pfandler 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  | slides  | system page  ]
  9. Bernhard Bliem, Günther Charwat, Markus Hecher and Stefan Woltran 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  ]
  10. Michael Abseher, Frederico Dusberger, Nysret Musliu and Stefan Woltran 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  ]
  11. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger and Stefan Woltran Computing Secure Sets in Graphs using Answer Set Programming In Journal of Logic and Computation, 2015.
    (Special issue of ASPOCP 2014)
    [ Abstract | BibTeX | pdf  ]
  12. Günther Charwat, Wolfgang Dvořák, Sarah Alice Gaggl, Johannes Peter Wallner and Stefan Woltran Methods for Solving Reasoning Problems in Abstract Argumentation - A Survey In Artificial Intelligence, 220 (0): 28-63, 2015.
    [ Abstract | BibTeX | doi  ]

2014

  1. Bernhard Bliem and Stefan Woltran Complexity of Secure Sets In CoRR, abs/1411.6549, 2014.
    [ BibTeX | pdf  ]
  2. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger, Markus Hecher and Stefan Woltran 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  ]
  3. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger, Markus Hecher and Stefan Woltran 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  ]
  4. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger and Stefan Woltran 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  ]
  5. Günther Charwat and Andreas Pfandler DEMOCRATIX: A Declarative Approach to Winner Determination In Fifth International Workshop on Computational Social Choice (COMSOC 2014), 2014.
    [ Abstract | BibTeX | pdf  | system page  ]
  6. Michael Abseher, Bernhard Bliem, Günther Charwat, Frederico Dusberger, Markus Hecher and Stefan Woltran D-FLAT: Progress Report Technical Report DBAI-TR-2014-86, DBAI, Vienna University of Technology, 2014.
    [ Abstract | BibTeX | pdf  ]

2013

  1. Bernhard Bliem, Reinhard Pichler and Stefan Woltran 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  ]
  2. Bernhard Bliem, Reinhard Pichler and Stefan Woltran 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

  1. Bernhard Bliem 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  ]
  2. Bernhard Bliem, Michael Morak and Stefan Woltran 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  ]
Top
Last updated: 2017-01-09 16:22

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Informationssysteme an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. / Disclaimer.