Project: Turning Theoretical Tractability into Efficient Computation via Datalog
(supported by the by the Austrian Science Fund (FWF) under grant P20704-N18)
Contents
Duration:
The project started at September 1, 2008 and the duration is 3 years.
Project team
Project Leader:
Project Staff:
Project Participants:
Goal of the project
Due to the rapid progress of business process automation and a pervasion of virtually all aspects of life by computers, computational solutions are needed for increasingly hard problems in a great variety of fields. However, the intractability of many practically important problems is a strong obstacle to the design of efficient solutions. Two major lines of research have been pursued in response to this situation:
- Parameterized complexity and the study of fixed-parameter algorithms have made a lot of progress in identifying tractable fragments of many hard problems. However, a theoretical tractability result does, in general, not automatically yield a computer program which actually runs efficiently in practice.
- Powerful tools have been making enormous progress in solving even intractable problems, among them most notably SAT solvers and datalog systems like DLV. However, a typical shortcoming of these tools is that, in general, they do not take advantage of tractable fragments of hard problems, i.e., although a problem instance falls into a theoretically easy subclass, the resources needed for solving it are essentially the same as with really hard problem instances.
Publications
| [1] | Uwe Egly, Sarah A. Gaggl, and Stefan Woltran. Answer-set programming encodings for argumentation frameworks. Argument & Computation, 1(2):147-177, 2010. [ bib ] |
| [2] | Georg Gottlob, Reinhard Pichler, and Fang Wei. Bounded treewidth as a key to tractability of knowledge representation and reasoning. Artif. Intell., 174(1):105-132, 2010. [ bib ] |
| [3] | Georg Gottlob, Reinhard Pichler, and Fang Wei. Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Logic, 12(1):3:1-3:48, 2010. [ bib ] |
| [4] | Georg Gottlob, Reinhard Pichler, and Fang Wei. Tractable database design and datalog abduction through bounded treewidth. Inf. Syst., 35(3):278-298, 2010. [ bib ] |
| [5] | Wolfgang Dvorák, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter tractable algorithms for argumentation. In Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning, (KR'10), Toronto, Ontario, Canada, May 9-13, 2010, pages 112-122. AAAI Press, 2010. [ bib ] |
| [6] | Wolfgang Dvorák, Stefan Szeider, and Stefan Woltran. Reasoning in argumentation frameworks of bounded clique-width. In Pietro Baroni, Federico Cerutti, Massimiliano Giacomin, and Guillermo R. Simari, editors, Proceedings of the 3rd International Conference on Computational Models of Argument, (COMMA'10), Desenzano del Garda, Italy, Septembr 8-10, 2010, volume 216 of Frontiers in Artificial Intelligence and Applications, pages 219-230. IOS Press, 2010. [ bib ] |
| [7] | Thomas Hammerl and Nysret Musliu. Ant colony optimization for tree decompositions. In Peter I. Cowling and Peter Merz, editors, Proceedings of the Evolutionary 10th European Conference on Computation in Combinatorial Optimization, (EvoCOP'10), Istanbul, Turkey, April 7-9, 2010, volume 6022 of Lecture Notes in Computer Science, pages 95-106. Springer, 2010. [ bib ] |
| [8] | Michael Morak, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. A dynamic-programming based asp-solver. In Tomi Janhunen and Ilkka Niemelä, editors, Proceedings of the 12th European Conference on Logics in Artificial Intelligence, (JELIA'10), Helsinki, Finland, September 13-15, 2010, volume 6341 of Lecture Notes in Computer Science, pages 369-372. Springer, 2010. [ bib | .pdf ] |
| [9] | Reinhard Pichler, Stefan Rümmele, Stefan Szeider, and Stefan Woltran. Tractable answer-set programming with weight constraints: Bounded treewidth is not enough. In Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Proceedings of the 12th International Conference on Principles of Knowledge Representation and Reasoning, (KR'10), Toronto, Ontario, Canada, May 9-13, 2010, pages 508-517. AAAI Press, 2010. [ bib | .pdf ] |
| [10] | Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Counting and enumeration problems with bounded treewidth. In Edmund M. Clarke and Andrei Voronkov, editors, Proceedings of the 16th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, (LPAR-16), April 25 - May 1, 2010, Dakar, Senegal, volume 6355 of Lecture Notes in Artificial Intelligence, pages 387-404. Springer, 2010. [ bib | .pdf ] |
| [11] | Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Multicut algorithms via tree decompositions. In Tiziana Calamoneri and Josep Díaz, editors, Proceedings of the 7th International Conference on Algorithms and Complexity, (CIAC'10), Rome, Italy, May 26-28, 2010, volume 6078 of Lecture Notes in Computer Science, pages 167-179. Springer, 2010. [ bib | .pdf ] |
| [12] | Reinhard Pichler and Stefan Woltran. The complexity of handling minimal solutions in logic-based abduction. In Helder Coelho, Rudi Studer, and Michael Wooldridge, editors, Proceedings of the 19th European Conference on Artificial Intelligence, (ECAI'10), Lisbon, Portugal, August 16-20, 2010, volume 215 of Frontiers in Artificial Intelligence and Applications, pages 895-900. IOS Press, 2010. [ bib ] |
| [13] | Miroslaw Truszczynski and Stefan Woltran. Relativized hyperequivalence of logic programs for modular programming. TPLP, 9(6):781-819, 2009. [ bib ] |
| [14] | Michael Jakl, Reinhard Pichler, and Stefan Woltran. Answer-set programming with bounded treewidth. In Craig Boutilier, editor, Proceedings of the 21st International Joint Conference on Artificial Intelligence, (IJCAI'09), Pasadena, California, USA, July 11-17, 2009, pages 816-822, 2009. [ bib | .pdf ] |
| [15] | Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Belief revision with bounded treewidth. In Esra Erdem, Fangzhen Lin, and Torsten Schaub, editors, Proceedings of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning, (LPNMR'09), Potsdam, Germany, September 14-18, 2009, volume 5753 of Lecture Notes in Computer Science, pages 250-263. Springer, 2009. [ bib | .pdf ] |
| [16] | Miroslaw Truszczynski and Stefan Woltran. Hyperequivalence of logic programs with respect to supported models. Ann. Math. Artif. Intell., 53(1-4):331-365, 2008. [ bib ] |
| [17] | Miki Hermann and Reinhard Pichler. Counting complexity of minimal cardinality and minimal weight abduction. In Steffen Hölldobler, Carsten Lutz, and Heinrich Wansing, editors, Proceedings of the 11th European Conference on Logics in Artificial Intelligence, (JELIA'08), September 28 - October 1, 2008, Dresden, Germany, volume 5293 of Lecture Notes in Computer Science, pages 206-218. Springer, 2008. [ bib | .pdf ] |
| [18] | Michael Jakl, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Fast counting with bounded treewidth. In Iliano Cervesato, Helmut Veith, and Andrei Voronkov, editors, Proceedings of the 15th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning, (LPAR'08), November 22-27, 2008, Doha, Qatar, volume 5330 of Lecture Notes in Computer Science, pages 436-450. Springer, 2008. [ bib | .pdf ] |
| [19] | Miroslaw Truszczynski and Stefan Woltran. Relativized hyperequivalence of logic programs for modular programming. In Maria Garcia de la Banda and Enrico Pontelli, editors, Proceedings of the 24th International Conference on Logic Programming, (ICLP'08), Udine, Italy, December 9-13, 2008, volume 5366 of Lecture Notes in Computer Science, pages 576-590. Springer, 2008. [ bib ] |
| [20] | Michael Jakl, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Fast counting with bounded treewidth. Technical Report DBAI-TR-2008-61, Technische Universität Wien, 2008. [ bib | .pdf ] |