Evaluating Answer Set Programming with Non-Convex Recursive Aggregates

• Autorzy: Alviano M.

Identyfikatory

DOI

10.3233/FI-2016-1441

• Konferencja: Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (22; 22.09.2015; Ferrara; Italy)
• Języki publikacji: EN

Abstrakty

EN

Aggregation functions are widely used in answer set programming (ASP) for representing and reasoning on knowledge involving sets of objects collectively. These sets may also depend recursively on the results of the aggregation functions, even if so far the support for such recursive aggregations was quite limited in ASP systems. In fact, recursion over aggregates was restricted to convex aggregates, i.e., aggregates that may have only one transition from false to true, and one from true to false, in this specific order. Recently, such a restriction has been overcome, so that the user can finally use non-convex recursive aggregates in ASP programs. An evaluation of ASP programs with non-convex recursive aggregates is reported in this paper, also testing a recently proposed extension of the concept of the positive extension graph to the case of programs with aggregates. Moreover, as an additional contribution, new rewritings for EVEN and ODD are presented: EVEN maps to true aggregation sets containing an even number of true literals, and ODD maps to true aggregation sets containing an odd number of true literals. Both aggregates are non-convex, and previously replaced by a conjunction of non-convex sums, whose size is quadratic with respect to the number of literals in the aggregation set. A different rewriting is presented in this paper, whose size is linear with respect to the number of literals in the aggregation set.

Słowa kluczowe

EN

answer set programming; aggregation function; nonconvex recursive aggregates

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2016
• Tom: Vol. 149, nr 1/2
• Strony: 1--34
• Opis fizyczny: Bibliogr. 48 poz., rys., tab., wykr.

Twórcy

autor

Alviano M.

• Department of Mathematics and Computer Science, University of Calabria, Via Pietro Bucci 30/B, 87036 Rende (CS), Italy

Bibliografia

• [1] Brewka G, Eiter T, Truszczynski M. Answer set programming at a glance. Commun ACM. 2011; 54(12):92–103. Available from: http://doi.acm.org/10.1145/2043174.2043195. doi:10.1145/2043174.2043195.
• [2] Gelfond M, Lifschitz V. The Stable Model Semantics for Logic Programming. In: Kowalski RA, Bowen KA, editors. Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (2 Volumes). MIT Press; 1988. p. 1070–1080.
• [3] Gelfond M, Lifschitz V. Classical Negation in Logic Programs and Disjunctive Databases. New Generation Comput. 1991;9(3/4):365–386. Available from: http://dx.doi.org/10.1007/BF03037169. doi:10.1007/BF03037169.
• [4] Bartholomew M, Lee J, Meng Y. First-Order Semantics of Aggregates in Answer Set Programming Via Modified Circumscription. In: Logical Formalizations of Commonsense Reasoning, Papers from the 2011 AAAI Spring Symposium, Technical Report SS-11-06, Stanford, California, USA, March 21-23, 2011. AAAI; 2011. Available from: http://www.aaai.org/ocs/index.php/SSS/SSS11/paper/view/2472.
• [5] Faber W, Pfeifer G, Leone N. Semantics and complexity of recursive aggregates in answer set programming. Artif Intell. 2011;175(1):278–298. Available from: http://dx.doi.org/10.1016/j.artint.2010.04.002. doi:10.1016/j.artint.2010.04.002.
• [6] Ferraris P. Logic programs with propositional connectives and aggregates. ACM Trans Comput Log. 2011;12(4):25. Available from: http://doi.acm.org/10.1145/1970398.1970401. doi:10.1145/1970398.1970401.
• [7] Gelfond M, Zhang Y. Vicious Circle Principle and Logic Programs with Aggregates. Theory and Practice of Logic Programming. 2014;14(4-5):587–601. Available from: http://dx.doi.org/10.1017/S1471068414000222. doi:10.1017/S1471068414000222.
• [8] Liu L, Pontelli E, Son TC, Truszczynski M. Logic programs with abstract constraint atoms: The role of computations. Artif Intell. 2010;174(3-4):295–315. Available from: http://dx.doi.org/10.1016/j.artint.2009.11.016. doi:10.1016/j.artint.2009.11.016.
• [9] Simons P, Niemelä I, Soininen T. Extending and implementing the stable model semantics. Artif Intell. 2002;138(1-2):181–234. Available from: http://dx.doi.org/10.1016/S0004-3702(02)00187-X. doi:10.1016/S0004-3702(02)00187-X.
• [10] Giunchiglia E, Lierler Y, Maratea M. Answer Set Programming Based on Propositional Satisfiability. J Autom Reasoning. 2006;36(4):345–377. Available from: http://dx.doi.org/10.1007/s10817-006-9033-2. doi:10.1007/s10817-006-9033-2.
• [11] Faber W, Pfeifer G, Leone N, Dell’Armi T, Ielpa G. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming. 2008;8(5-6):545–580. Available from: http://dx.doi.org/10.1017/S1471068408003323. doi:10.1017/S1471068408003323.
• [12] Gebser M, Kaufmann B, Schaub T. Conflict-driven answer set solving: From theory to practice. Artif Intell. 2012;187:52–89. Available from: http://dx.doi.org/10.1016/j.artint.2012.04.001. doi:10.1016/j.artint.2012.04.001.
• [13] Alviano M, Dodaro C, Faber W, Leone N, Ricca F. WASP: A Native ASP Solver Based on Constraint Learning. In: Cabalar P, Son TC, editors. Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings. vol. 8148 of Lecture Notes in Computer Science. Springer; 2013. p. 54–66. Available from: http://dx.doi.org/10.1007/978-3-642-40564-8_6. doi:10.1007/978-3-642-40564-8_6.
• [14] Alviano M, Dodaro C, Leone N, Ricca F. Advances in WASP. In: Calimeri F, Ianni G, Truszczynski M, editors. Logic Programming and Nonmonotonic Reasoning - 13th International Conference, LPNMR 2015, Lexington, KY, USA, September 27-30, 2015. Proceedings. vol. 9345 of Lecture Notes in Computer Science. Springer; 2015. p. 40–54. Available from: http://dx.doi.org/10.1007/978-3-319-23264-5_5. doi:10.1007/978-3-319-23264-5 _5.
• [15] Pelov N, Denecker M, Bruynooghe M. Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming. 2007;7(3):301–353. Available from: http://dx.doi.org/10.1017/S1471068406002973. doi:10.1017/S1471068406002973.
• [16] Shen Y, Wang K, Eiter T, Fink M, Redl C, Krennwallner T, et al. FLP answer set semantics without circular justifications for general logic programs. Artif Intell. 2014;213:1–41. Available from: http://dx.doi.org/10.1016/j.artint.2014.05.001. doi:10.1016/j.artint.2014.05.001.
• [17] Son TC, Pontelli E. A Constructive semantic characterization of aggregates in answer set programming. Theory and Practice of Logic Programming. 2007;7(3):355–375. Available from: http://dx.doi.org/10.1017/S1471068406002936. doi:10.1017/S1471068406002936.
• [18] Liu L, Truszczynski M. Properties and Applications of Programs with Monotone and Convex Constraints. J Artif Intell Res (JAIR). 2006;27:299–334. Available from: http://dx.doi.org/10.1613/jair.2009. doi:10.1613/jair.2009.
• [19] Alviano M, Faber W. The Complexity Boundary of Answer Set Programming with Generalized Atoms under the FLP Semantics. In: Cabalar P, Son TC, editors. Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings. vol. 8148 of Lecture Notes in Computer Science. Springer; 2013. p. 67–72. Available from: http://dx.doi.org/10.1007/978-3-642-40564-8_7.
• [20] Abseher M, Bliem B, Charwat G, Dusberger F, Woltran S. Computing Secure Sets in Graphs using Answer Set Programming. In: Inclezan D, Maratea M, editors. Seventh International Workshop on Answer Set Programming and Other Computing Paradigms (ASPOCP 2014); 2014.
• [21] Eiter T, Fink M, Krennwallner T, Redl C. Conflict-driven ASP solving with external sources. Theory and Practice of Logic Programming. 2012;12(4-5):659–679. Available from: http://dx.doi.org/10.1017/S1471068412000233. doi:10.1017/S1471068412000233.
• [22] Eiter T, Ianni G, Lukasiewicz T, Schindlauer R, Tompits H. Combining answer set programming with description logics for the Semantic Web. Artif Intell. 2008;172(12-13):1495–1539. Available from: http://dx.doi.org/10.1016/j.artint.2008.04.002. doi:10.1016/j.artint.2008.04.002.
• [23] Berman P, Karpinski M, Larmore LL, Plandowski W, Rytter W. On the Complexity of Pattern Matching for Highly Compressed Two-Dimensional Texts. J Comput Syst Sci. 2002;65(2):332–350. Available from: http://dx.doi.org/10.1006/jcss.2002.1852. doi:10.1006/jcss.2002.1852.
• [24] Brigham RC, Dutton RD, Hedetniemi ST. Security in graphs. Discrete Applied Mathematics. 2007; 155(13):1708-1714. Available from: http://www.sciencedirect.com/science/article/pii/S0166218X07000558. doi:http://dx.doi.org/10.1016/j.dam.2007.03.009.
• [25] Abseher M, Bliem B, Charwat G, Dusberger F, Woltran S. Computing secure sets in graphs using answer set programming. Journal of Logic and Computation. 2015; Available from: http://logcom.oxfordjournals.org/content/early/2015/08/31/logcom.exv060.abstract. doi:10.1093/logcom/exv060.
• [26] Alviano M, Faber W, Gebser M. Rewriting recursive aggregates in answer set programming: back to monotonicity. TPLP. 2015;15(4-5):559–573. Available from: http://dx.doi.org/10.1017/S1471068415000228. doi:10.1017/S1471068415000228.
• [27] Ferraris P. Answer Sets for Propositional Theories. In: Baral C, Greco G, Leone N, Terracina G, editors. Proceedings of the Eighth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR’05). vol. 3662 of Lecture Notes in Artificial Intelligence. Springer-Verlag; 2005. p. 119–131.
• [28] Lifschitz V, Pearce D, Valverde A. Strongly equivalent logic programs. ACM Transactions on Computational Logic. 2001;2(4):526–541.
• [29] Turner H. Strong equivalence made easy: nested expressions and weight constraints. Theory and Practice of Logic Programming. 2003;3(4-5):609–622.
• [30] Alviano M. Evaluating Answer Set Programming with Non-Convex Recursive Aggregates. In: Bistarelli S, Formisano A, Maratea M, editors. Proceedings of the 22nd RCRA International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion 2015 (RCRA 2015) A workshop of the XIV International Conference of the Italian Association for Artificial Intelligence (AI*IA 2015), Ferrara, Italy, September 22, 2015.. vol. 1451 of CEUR Workshop Proceedings. CEUR-WS.org; 2015. p. 1–15. Available from: http://ceur-ws.org/Vol-1451/paper1.pdf.
• [31] Gebser M, Kaminski R, König A, Schaub T. Advances in gringo Series 3. In: Delgrande JP, Faber W, editors. LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings. vol. 6645 of Lecture Notes in Computer Science. Springer; 2011. p. 345–351. Available from: http://dx.doi.org/10.1007/978-3-642-20895-9_39. doi:10.1007/978-3-642-20895-9 _39.
• [32] Barrett CW, Sebastiani R, Seshia SA, Tinelli C. Satisfiability Modulo Theories. In: Biere A, Heule M, van Maaren H, Walsh T, editors. Handbook of Satisfiability. vol. 185 of Frontiers in Artificial Intelligence and Applications. IOS Press; 2009. p. 825–885. Available from: http://dx.doi.org/10.3233/978-1-58603-929-5-825. doi:10.3233/978-1-58603-929-5-825.
• [33] Eiter T, Fink M, Krennwallner T, Redl C, Schüller P. Efficient HEX-Program Evaluation Based on Unfounded Sets. J Artif Intell Res (JAIR). 2014;49:269–321. Available from: http://dx.doi.org/10.1613/jair.4175. doi:10.1613/jair.4175.
• [34] Eiter T, Tompits H, Woltran S. On Solution Correspondences in Answer Set Programming. In: Kaelbling L, Saffiotti A, editors. Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence (IJCAI’05). Professional Book Center; 2005. p. 97–102.
• [35] Janhunen T, Niemelä I. Applying Visible Strong Equivalence in Answer-Set Program Transformations. In: Erdem E, Lee J, Lierler Y, Pearce D, editors. Correct Reasoning: Essays on Logic-Based AI in Honour of Vladimir Lifschitz. vol. 7265 of Lecture Notes in Computer Science. Springer-Verlag; 2012. p. 363–379.
• [36] Faber W, Leone N, Maratea M, Ricca F. Look-back Techniques for ASP Programs with Aggregates. Fundam Inform. 2011;107(4):379–413. Available from: http://dx.doi.org/10.3233/FI-2011-408. doi:10.3233/FI-2011-408.
• [37] Alviano M, Greco G, Leone N. Dynamic Magic Sets for Programs with Monotone Recursive Aggregates. In: Delgrande JP, Faber W, editors. Logic Programming and Nonmonotonic Reasoning - 11th International Conference, LPNMR 2011, Vancouver, Canada, May 16-19, 2011. Proceedings. vol. 6645 of Lecture Notes in Computer Science. Springer; 2011. p. 148–160. Available from: http://dx.doi.org/10.1007/978-3-642-20895-9_14. doi:10.1007/978-3-642-20895-9 _14.
• [38] Alviano M, Calimeri F, Faber W, Leone N, Perri S. Unfounded Sets and Well-Founded Semantics of Answer Set Programs with Aggregates. J Artif Intell Res (JAIR). 2011;42:487–527. Available from: http://dx.doi.org/10.1613/jair.3432. doi:10.1613/jair.3432.
• [39] Alviano M. Efficient recursive aggregate evaluation in logic programming. Intelligenza Artificiale. 2011;5(2):207–215. Available from: http://dx.doi.org/10.3233/IA-2011-0023. doi:10.3233/IA-2011-0023.
• [40] Alviano M, Leone N. Complexity and compilation of GZ-aggregates in answer set programming. TPLP. 2015;15(4-5):574–587. Available from: http://dx.doi.org/10.1017/S147106841500023X. doi:10.1017/S147106841500023X.
• [41] Alviano M, Calimeri F, Charwat G, Dao-Tran M, Dodaro C, Ianni G, et al. The Fourth Answer Set Programming Competition: Preliminary Report. In: Cabalar P, Son TC, editors. LPNMR. LNCS; 2013. p. 42–53.
• [42] Ben-Eliyahu R, Dechter R. Propositional Semantics for Disjunctive Logic Programs. Ann Math Artif Intell. 1994;12(1-2):53–87. Available from: http://dx.doi.org/10.1007/BF01530761. doi:10.1007/BF01530761.
• [43] Marx D. Complexity of clique coloring and related problems. Theor Comput Sci. 2011;412(29):3487–3500.
• [44] Liu G, You J. Relating weight constraint and aggregate programs: Semantics and representation. Theory and Practice of Logic Programming. 2013;13(1):1–31. Available from: http://dx.doi.org/10.1017/S147106841100038X. doi:10.1017/S147106841100038X.
• [45] Ferraris P, Lifschitz V. Weight constraints as nested expressions. Theory and Practice of Logic Programming. 2005;5(1-2):45–74. Available from: http://dx.doi.org/10.1017/S1471068403001923. doi:10.1017/S1471068403001923.
• [46] Bomanson J, Janhunen T. Normalizing Cardinality Rules Using Merging and Sorting Constructions. vol. 8148 of Lecture Notes in Computer Science. Springer; 2013. p. 187–199. Available from: http://dx.doi.org/10.1007/978-3-642-40564-8_19. doi:10.1007/978-3-642-40564-8 _19.
• [47] Bomanson J, Gebser M, Janhunen T. Improving the Normalization of Weight Rules in Answer Set Programs. In: Fermé E, Leite J, editors. JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings. vol. 8761 of Lecture Notes in Computer Science. Springer; 2014. p. 166–180. Available from: http://dx.doi.org/10.1007/978-3-319-11558-0_12. doi:10.1007/978-3-319-11558-0 _12.
• [48] Alviano M, Faber W. Supportedly Stable Answer Sets for Logic Programs with Generalized Atoms. In: ten Cate B, Mileo A, editors. Web Reasoning and Rule Systems - 9th International Conference, RR 2015, Berlin, Germany, August 4-5, 2015, Proceedings. vol. 9209 of Lecture Notes in Computer Science. Springer; 2015. p. 30–44. Available from: http://dx.doi.org/10.1007/978-3-319-22002-4_4. doi:10.1007/978-3-319-22002-4_ 4.

Uwagi

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