D-FLAT^2 : Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy

• Autorzy: Bliem B. , Charwat G. , Hecher M. , Woltran S.

Identyfikatory

DOI

10.3233/FI-2016-1397

• Konferencja: ASPOCP 2015 : ASPOCP International Workshop on “Answer Set Programming and Other Computing Paradigms” (8: August 31, 2015: Cork, Ireland)
• Języki publikacji: EN

Abstrakty

EN

Many problems from the area of AI have been shown tractable for bounded treewidth. In order to put such results into practice, quite involved dynamic programming (DP) algorithms on tree decompositions have to be designed and implemented. These algorithms typically show recurring patterns that call for tasks like subset minimization. In this paper we present a novel approach to obtain such DP algorithms from simpler principles, where the DP formalization of subset minimization is performed automatically. We first give a theoretical account of our novel method, and then present D-FLAT^2, a system that allows one to specify the core DP algorithm via answer set programming (ASP). We illustrate the approach at work by providing several DP algorithms that are more space-efficient than existing solutions, while featuring improved readability, reuse and therefore maintainability of ASP code. Experiments show that our approach also yields a significant improvement in runtime performance.

Słowa kluczowe

EN

subset minimization; dynamic programming; tree decomposition; answer set programming; artificial intelligence

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 147, nr 1
• Strony: 27--61
• Opis fizyczny: Bibliogr. 35 poz., rys., tab., wykr.

Twórcy

autor

Bliem B.

• Institute of Information Systems, TU Wien, Austria

autor

Charwat G.

• Institute of Information Systems, TU Wien, Austria

autor

Hecher M.

• Institute of Information Systems, TU Wien, Austria

autor

Woltran S.

• Institute of Information Systems, TU Wien, Austria

Bibliografia

• [1] Courcelle B. The Monadic Second-Order Logic of Graphs. I. Recognizable Sets of Finite Graphs. Inf Comput. 1990;85(1):12–75. doi:10.1016/0890-5401(90)90043-H.
• [2] Kneis J, Langer A, Rossmanith P. Courcelle’s Theorem – A Game-Theoretic Approach. Discrete Optimization. 2011;8(4):568–594. doi:10.1016/j.disopt.2011.06.001.
• [3] Niedermeier R. Invitation to Fixed-Parameter Algorithms. Oxford Lecture Series in Mathematics and its Applications. OUP; 2006. Available from: https://global.oup.com/academic/product/invitation-to-fixed-parameter-algorithms-9780198566076.
• [4] Cygan M, Fomin FV, Kowalik L, Lokshtanov D, Marx D, Pilipczuk M, et al. Parameterized Algorithms. Springer; 2015. doi:10.1007/978-3-319-21275-3.
• [5] Dvořák W, Pichler R, Woltran S. Towards Fixed-Parameter Tractable Algorithms for Abstract Argumentation. Artif Intell. 2012;186:1–37. doi:10.1016/j.artint.2012.03.005.
• [6] Jakl M, Pichler R, Woltran S. Answer-Set Programming with Bounded Treewidth. In: Proc. IJCAI; 2009. p. 816–822. Available from: http://ijcai.org/Proceedings/09/Papers/140.pdf.
• [7] Jakl M, Pichler R, Rümmele S, Woltran S. Fast Counting with Bounded Treewidth. In: Proc. LPAR. vol. 5330 of LNCS. Springer; 2008. p. 436–450. doi:10.1007/978-3-540-89439-1_31.
• [8] Gottlob G, Pichler R, Wei F. Tractable Database Design and Datalog Abduction through Bounded Treewidth. Inf Syst. 2010;35(3):278–298. doi:10.1016/j.is.2009.09.003.
• [9] Abseher M, Bliem B, Charwat G, Dusberger F, Hecher M, Woltran S. The D-FLAT System for Dynamic Programming on Tree Decompositions. In: Proc. JELIA. vol. 8761 of LNCS; 2014. p. 558–572. doi:10.1007/978-3-319-11558-0_39.
• [10] Courcelle B, Durand I. Computations by Fly-Automata beyond Monadic Second-Order Logic. CoRR. 2013;abs/1305.7120. Available from: http://arxiv.org/abs/1305.7120.
• [11] Brewka G, Eiter T, Truszczyński M. Answer Set Programming at a Glance. Commun ACM. 2011;54(12):92–103. doi:10.1145/2043174.2043195.
• [12] Leone N, Pfeifer G, Faber W, Eiter T, Gottlob G, Perri S, et al. The DLV System for Knowledge Representation and Reasoning. ACM Trans Comput Log. 2006;7(3):499–562. doi:10.1145/1149114.1149117.
• [13] Eiter T, Polleres A. Towards Automated Integration of Guess and Check Programs in Answer Set Programming: A Meta-Interpreter and Applications. TPLP. 2006;6(1-2):23–60. doi:10.1017/S1471068405002577.
• [14] Gebser M, Kaminski R, Schaub T. Complex Optimization in Answer Set Programming. TPLP. 2011;11(4-5):821–839. doi:10.1017/S1471068411000329.
• [15] Brewka G, Delgrande JP, Romero J, Schaub T. asprin: Customizing Answer Set Preferences without a Headache. In: Proc. AAAI. AAAI Press; 2015. p. 1467–1474. Available from: http://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/view/9535.
• [16] Samer M, Szeider S. Algorithms for Propositional Model Counting. J Discrete Algorithms. 2010;8(1):50–64. doi:10.1016/j.jda.2009.06.002.
• [17] Bliem B, Charwat G, Hecher M, Woltran S. D-FLATˆ2: Subset Minimization in Dynamic Programming on Tree Decompositions Made Easy. In: Proc. ASPOCP’15; 2015. Available from: https://sites.google.com/site/aspocp2015/ASPOCP2015paper4.pdf.
• [18] Bliem B, Charwat G, Hecher M, Woltran S. Subset Minimization in Dynamic Programming on Tree Decompositions. In: AAAI-16 Workshop on Beyond NP; 2016. Available from: http://www.aaai.org/ocs/index.php/WS/AAAIW16/paper/download/12562/12380.
• [19] Downey RG, Fellows MR. Parameterized Complexity. Monographs in Computer Science. Springer; 1999. doi:10.1007/978-1-4612-0515-9.
• [20] Robertson N, Seymour PD. Graph minors. III. Planar Tree-Width. J Comb Theory, Ser B. 1984;36(1):49–64. doi:10.1016/0095-8956(84)90013-3.
• [21] Arnborg S, Corneil DG, Proskurowski A. Complexity of Finding Embeddings in a k-Tree. SIAM J Algebraic Discrete Methods. 1987;8(2):277–284. doi:10.1137/0608024.
• [22] Bodlaender HL. A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth. SIAM J Comput. 1996;25(6):1305–1317. doi:10.1137/S0097539793251219.
• [23] Dechter R. Constraint Processing. Morgan Kaufmann; 2003. Available from: https://www.elsevier.com/books/constraint-processing/dechter/978-1-55860-890-0.
• [24] Dermaku A, Ganzow T, Gottlob G, McMahan BJ, Musliu N, Samer M. Heuristic Methods for Hypertree Decomposition. In: Proc. MICAI. vol. 5317 of LNCS. Springer; 2008. p. 1–11. doi:10.1007/978-3-540-88636-5_1.
• [25] Bodlaender HL, Koster AMCA. Treewidth Computations I. Upper Bounds. Inf Comput. 2010;208(3):259–275. doi:10.1016/j.ic.2009.03.008.
• [26] Kloks T. Treewidth, Computations and Approximations. vol. 842 of LNCS. Springer; 1994. doi:10.1007/BFb0045375.
• [27] Gebser M, Kaufmann B, Kaminski R, Ostrowski M, Schaub T, Schneider MT. Potassco: The Potsdam Answer Set Solving Collection. AI Commun. 2011;24(2):107–124. doi:10.3233/AIC-2011-0491.
• [28] Abseher M, Bliem B, Charwat G, Dusberger F, Hecher M, Woltran S. D-FLAT: Progress Report. TU Wien; 2014. DBAI-TR-2014-86. Available from: https://dbai.tuwien.ac.at/research/report/dbai-tr-2014-86.pdf.
• [29] McCarthy J. Circumscription – A Form of Non-Monotonic Reasoning. Artif Intell. 1980;13(1-2):27–39. doi:10.1016/0004-3702(80)90011-9.
• [30] Pearce D, Tompits H, Woltran S. Characterising Equilibrium Logic and Nested Logic Programs: Reductions and Complexity. TPLP. 2009;9(5):565–616. doi:10.1017/S147106840999010X.
• [31] Dung PM. On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artif Intell. 1995;77(2):321–357. doi:10.1016/0004-3702(94)00041-X.
• [32] Egly U, Gaggl SA, Woltran S. Answer-Set Programming Encodings for Argumentation Frameworks. Argument and Computation. 2010;1(2):147–177. doi:10.1080/19462166.2010.486479.
• [33] Lonsing F, Egly U. DepQBF: An Incremental QBF Solver Based on Clause Groups. CoRR. 2015;abs/1502.02484. Available from: http://arxiv.org/abs/1502.02484.
• [34] Heule M, Seidl M, Biere A. A Unified Proof System for QBF Preprocessing. In: Proc. IJCAR. vol. 8562 of LNCS. Springer; 2014. p. 91–106. doi:10.1007/978-3-319-08587-6_7.
• [35] Langer A, Reidl F, Rossmanith P, Sikdar S. Evaluation of an MSO-Solver. In: Proc. ALENEX. SIAM /Omnipress; 2012. p. 55–63. doi:10.1137/1.9781611972924.5.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).