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] | G. Erdélyi, M. Lackner, and A. Pfandler. Computational Aspects of Nearly Single-Peaked Electorates. ArXiv e-prints, November 2012. [ bib | arXiv ] |
| [2] | Leo Brueggeman, Michael R. Fellows, Rudolf Fleischer, Martin Lackner, Christian Komusiewicz, Yiannis Koutis, Andreas Pfandler, and Frances A. Rosamond. Train marshalling is fixed parameter tractable. In Evangelos Kranakis, Danny Krizanc, and Flaminia Luccio, editors, Proc. FUN 2012, volume 7288 of Lecture Notes in Computer Science, pages 51-56. Springer Berlin / Heidelberg, 2012. [ bib | .pdf ] |
| [3] | Gábor Erdélyi, Martin Lackner, and Andreas Pfandler. The complexity of nearly single-peaked consistency. In Proc. COMSOC 2012, 2012. [ bib | .pdf ] |
| [4] | Martin Lackner, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Multicut on graphs of bounded clique-width. In Guohui Lin, editor, Proc. COCOA 2012, volume 7402 of Lecture Notes in Computer Science, pages 115-126. Springer Berlin / Heidelberg, 2012. [ bib | .pdf ] |
| [5] | Marie-Louise Bruner and Martin Lackner. A fast algorithm for permutation pattern matching based on alternating runs. In Fedor Fomin and Petteri Kaski, editors, Proc. SWAT 2012, volume 7357 of Lecture Notes in Computer Science, pages 261-270. Springer Berlin / Heidelberg, 2012. [ bib | .pdf ] |
| [6] | Martin Lackner and Andreas Pfandler. Fixed-parameter algorithms for finding minimal models. In Gerhard Brewka, Thomas Eiter, and Sheila A. McIlraith, editors, Proc. KR 2012, pages 85-95. AAAI Press, 2012. [ bib | http ] |
| [7] | Martin Lackner and Andreas Pfandler. Fixed-parameter algorithms for closed world reasoning. In Luc De Raedt, Christian Bessière, Didier Dubois, Patrick Doherty, Paolo Frasconi, Fredrik Heintz, and Peter J. F. Lucas, editors, Proc. ECAI 2012, pages 492-497. IOS Press, 2012. [ bib | .pdf ] |
| [8] | Nadia Creignou, Odile Papini, Reinhard Pichler, and Stefan Woltran. Belief revision within fragments of propositional logic. In Knowledge Representation and Reasoning Conference, 2012. [ bib | http ] |
| [9] | Wolfgang Dvorák, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter tractable algorithms for abstract argumentation. Artificial Intelligence, 186(0):1 - 37, 2012. [ bib | DOI | http | .pdf ] |
| [10] | Pablo Barceló and Reinhard Pichler, editors. Datalog in Academia and Industry - Second International Workshop, Datalog 2.0, Vienna, Austria, September 11-13, 2012. Proceedings, volume 7494 of Lecture Notes in Computer Science. Springer, 2012. [ bib ] |
| [11] | Nadia Creignou, Odile Papini, Reinhard Pichler, and Stefan Woltran. Belief revision within fragments of propositional logic. In Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14, 2012. AAAI Press, 2012. [ bib | http ] |
| [12] | Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries. J. Comput. Syst. Sci., 2012. to appear. [ bib | .pdf ] |
| [13] | Reinhard Pichler, Stefan Rümmele, Stefan Szeider, and Stefan Woltran. Tractable answer-set programming with weight constraints: Bounded treewidth is not enough. TPLP, 2012. to appear. [ bib | .pdf ] |
| [14] | Michael R. Fellows, Andreas Pfandler, Frances A. Rosamond, and Stefan Rümmele. The parameterized complexity of abduction. In Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, July 22-26, 2012, Toronto, Ontario, Canada, 2012. [ bib | http ] |
| [15] | Reinhard Pichler, Stefan Rümmele, Stefan Szeider, and Stefan Woltran. Tractable answer-set programming with weight constraints: Bounded treewidth is not enough. CoRR, abs/1204.3040, 2012. [ bib | http ] |
| [16] | Michael Morak, Nysret Musliu, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Evaluating tree-decomposition based algorithms for answer set programming. In Learning and Intelligent Optimization - 6th International Conference, LION 6, Paris, France, January 16-20, 2012., volume 7219 of Lecture Notes in Computer Science. Springer, 2012. [ bib | .pdf ] |
| [17] | Michael Morak, Nysret Musliu, Stefan Rümmele, Stefan Woltran, and Reinhard Pichler. Evaluating tree-decomposition based algorithms for answer set programming. Technical Report DBAI-TR-2011-73, Technische Universität Wien, 2011. [ bib | .html | .pdf ] |
| [18] | Michael Morak, Nysret Musliu, Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. A new tree-decomposition based algorithm for answer set programming. In IEEE 23rd International Conference on Tools with Artificial Intelligence, ICTAI 2011, Boca Raton, FL, USA, November 7-9, 2011, pages 916-918. IEEE, 2011. [ bib | .pdf ] |
| [19] | Marie-Louise Bruner and Martin Lackner. A w[1]-completeness result for generalized permutation pattern matching. CoRR, abs/1109.1951, 2011. [ bib | http ] |
| [20] | Nadia Creignou, Johannes Schmidt, Michael Thomas, and Stefan Woltran. Complexity of logic-based argumentation in post's framework. Argument and Computation, 2(2-3):107-129, 2011. [ bib | .pdf ] |
| [21] | Wolfgang Dvorák, Paul E. Dunne, and Stefan Woltran. Parametric properties of ideal semantics. In IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011, pages 851-856. IJCAI/AAAI, 2011. [ bib | .pdf ] |
| [22] | Wolfgang Dvorák, Michael Morak, Clemens Nopp, and Stefan Woltran. dynpartix - a dynamic programming reasoner for abstract argumentation. CoRR, abs/1108.4804, 2011. [ bib | http ] |
| [23] | Nysret Musliu. Constructing cyclic staff schedules by iterated local search (extended abstract). In Proceedings MIC 2011, pages 655-657, 2011. [ bib | .pdf ] |
| [24] | Reinhard Pichler and Sebastian Skritek. Tractable counting of the answers to conjunctive queries. In Pablo Barceló and Val Tannen, editors, Proceedings of the 5th Alberto Mendelzon International Workshop on Foundations of Data Management, Santiago, Chile, May 9-12, 2011, volume 749 of CEUR Workshop Proceedings. CEUR-WS.org, 2011. [ bib | .pdf ] |
| [25] | Reinhard Pichler and Sebastian Skritek. The complexity of evaluating tuple generating dependencies. In Tova Milo, editor, Database Theory - ICDT 2011, 14th International Conference, Uppsala, Sweden, March 21-24, 2011, Proceedings, pages 244-255. ACM, 2011. [ bib | .pdf ] |
| [26] | Uwe Egly, Sarah A. Gaggl, and Stefan Woltran. Answer-set programming encodings for argumentation frameworks. Argument & Computation, 1(2):147-177, 2010. [ bib | http | .pdf ] |
| [27] | 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 | http | .pdf ] |
| [28] | Georg Gottlob, Reinhard Pichler, and Fang Wei. Monadic datalog over finite structures of bounded treewidth. ACM Trans. Comput. Log., 12(1):3, 2010. [ bib | .pdf ] |
| [29] | Georg Gottlob, Reinhard Pichler, and Fang Wei. Tractable database design and datalog abduction through bounded treewidth. Inf. Syst., 35(3):278-298, 2010. [ bib | .pdf ] |
| [30] | Wolfgang Dvorák, Reinhard Pichler, and Stefan Woltran. Towards fixed-parameter tractable algorithms for argumentation. In Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski, editors, Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010, pages 112-122. AAAI Press, 2010. [ bib | .pdf ] |
| [31] | 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 | .pdf ] |
| [32] | 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 | .pdf ] |
| [33] | 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 ] |
| [34] | 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 ] |
| [35] | 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 ] |
| [36] | 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 ] |
| [37] | 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 | .pdf ] |
| [38] | Miki Hermann and Reinhard Pichler. Counting complexity of propositional abduction. J. Comput. Syst. Sci., 76(7):634-649, 2010. [ bib | .pdf ] |
| [39] | Reinhard Pichler, Stefan Rümmele, and Stefan Woltran. Multicut algorithms via tree decompositions. Technical Report DBAI-TR-2010-67, Technische Universität Wien, 2010. [ bib | .html | .pdf ] |
| [40] | Miroslaw Truszczynski and Stefan Woltran. Relativized hyperequivalence of logic programs for modular programming. TPLP, 9(6):781-819, 2009. [ bib | .pdf ] |
| [41] | 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 ] |
| [42] | 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 ] |
| [43] | 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 | .pdf ] |
| [44] | 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 ] |
| [45] | 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 ] |
| [46] | 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 | .pdf ] |
| [47] | 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 ] |
| [48] | Thomas Hammerl, Nysret Musliu, and Werner Schafhauser. Metaheuristic algorithms and tree decomposition. In Handbook of Computational Intelligence. To appear. [ bib ] |