Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T11:40:05.307Z Has data issue: false hasContentIssue false
  • English
  • Français

Complexity and compilation of GZ-aggregates in answer set programming

Published online by Cambridge University Press:  03 September 2015

MARIO ALVIANO  and
NICOLA LEONE
MARIO ALVIANO
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Italy
NICOLA LEONE
Affiliation:
Department of Mathematics and Computer Science, University of Calabria, Italy
Get access Rights & Permissions [Opens in a new window]

Abstract

Gelfond and Zhang recently proposed a new stable model semantics based on Vicious Circle Principle in order to improve the interpretation of logic programs with aggregates. The paper focuses on this proposal, and analyzes the complexity of both coherence testing and cautious reasoning under the new semantics. Some surprising results highlight similarities and differences versus mainstream stable model semantics for aggregates. Moreover, the paper reports on the design of compilation techniques for implementing the new semantics on top of existing ASP solvers, which eventually lead to realize a prototype system that allows for experimenting with Gelfond-Zhang's aggregates.

Keywords

answer set programmingaggregatescomplexitycompilation
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 15 , Special Issue 4-5: 31st International Conference on Logic Programming , July 2015 , pp. 574 - 587
Copyright
Copyright © Cambridge University Press 2015 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Alviano, M., Dodaro, C., Faber, W., Leone, N. and Ricca, F. 2013. WASP: A native ASP solver based on constraint learning. In Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 54–66.Google Scholar
Alviano, M., Dodaro, C. and Ricca, F. 2014. Anytime computation of cautious consequences in answer set programming. Theory and Practice of Logic Programming 14, 4–5, 755–770.Google Scholar
Alviano, M. and Faber, W. 2013. The complexity boundary of answer set programming with generalized atoms under the FLP semantics. In Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 67–72.Google Scholar
Alviano, M. and Faber, W. 2015. Stable model semantics of abstract dialectical frameworks revisited: A logic programming perspective. In Proceedings of the 21st International Joint Conference on Artificial Intelligence. IJCAI Organization, Buenos Aires, Argentina, To appear.Google Scholar
Bartholomew, M., Lee, J. and Meng, Y. 2011. 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.Google Scholar
Bomanson, J., Gebser, M. and Janhunen, T. 2014. Improving the normalization of weight rules in answer set programs. In Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, Fermé, E. and Leite, J., Eds. Lecture Notes in Computer Science, vol. 8761. Springer, 166–180.Google Scholar
Bomanson, J. and Janhunen, T. 2013. Normalizing cardinality rules using merging and sorting constructions. In Logic Programming and Nonmonotonic Reasoning, 12th International Conference, LPNMR 2013, Corunna, Spain, September 15-19, 2013. Proceedings, Cabalar, P. and Son, T. C., Eds. Lecture Notes in Computer Science, vol. 8148. Springer, 187–199.CrossRefGoogle Scholar
Brewka, G., Eiter, T. and Truszczynski, M. 2011. Answer set programming at a glance. Commun. ACM 54, 12, 92–103.Google Scholar
Dantsin, E., Eiter, T., Gottlob, G. and Voronkov, A. 2001. Complexity and expressive power of logic programming. ACM Comput. Surv. 33, 3, 374–425.Google Scholar
Eiter, T., Fink, M., Krennwallner, T., Redl, C. and Schüller, P. 2014. Efficient hex-program evaluation based on unfounded sets. J. Artif. Intell. Res. (JAIR) 49, 269–321.CrossRefGoogle Scholar
Eiter, T. and Gottlob, G. 1995. On the computational cost of disjunctive logic programming: Propositional case. Ann. Math. Artif. Intell. 15, 3–4, 289–323.Google Scholar
Eiter, T., Ianni, G., Lukasiewicz, T., Schindlauer, R. and Tompits, H. 2008. Combining answer set programming with description logics for the semantic web. Artif. Intell. 172, 12–13, 1495–1539.Google Scholar
Faber, W., Pfeifer, G. and Leone, N. 2011. Semantics and complexity of recursive aggregates in answer set programming. Artif. Intell. 175, 1, 278–298.CrossRefGoogle Scholar
Faber, W., Pfeifer, G., Leone, N., Dell'Armi, T. and Ielpa, G. 2008. Design and implementation of aggregate functions in the DLV system. Theory and Practice of Logic Programming 8, 5–6, 545–580.Google Scholar
Ferraris, P. 2005. Answer sets for propositional theories. In Logic Programming and Nonmonotonic Reasoning, 8th International Conference, LPNMR 2005, Diamante, Italy, September 5-8, 2005, Proceedings, Baral, C., Greco, G., Leone, N., and Terracina, G., Eds. Lecture Notes in Computer Science, vol. 3662. Springer, 119–131.Google Scholar
Ferraris, P. 2011. Logic programs with propositional connectives and aggregates. ACM Trans. Comput. Log. 12, 4, 25.Google Scholar
Gebser, M., Kaufmann, B. and Schaub, T. 2012. Conflict-driven answer set solving: From theory to practice. Artif. Intell. 187, 52–89.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15-19, 1988 (2 Volumes), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1991. Classical negation in logic programs and disjunctive databases. New Generation Comput. 9, 3/4, 365–386.Google Scholar
Gelfond, M. and Zhang, Y. 2014. Vicious circle principle and logic programs with aggregates. Theory and Practice of Logic Programming 14, 4–5, 587–601.Google Scholar
Janhunen, T. 2006. Some (in)translatability results for normal logic programs and propositional theories. Journal of Applied Non-Classical Logics 16, 1–2, 35–86.Google Scholar
Lee, J. and Palla, R. 2009. System f2lp - computing answer sets of first-order formulas. In Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14-18, 2009. Proceedings, Erdem, E., Lin, F., and Schaub, T., Eds. Lecture Notes in Computer Science, vol. 5753. Springer, 515–521.Google Scholar
Liu, L., Pontelli, E., Son, T. C. and Truszczynski, M. 2010. Logic programs with abstract constraint atoms: The role of computations. Artif. Intell. 174, 3–4, 295–315.Google Scholar
Liu, L. and Truszczynski, M. 2006. Properties and applications of programs with monotone and convex constraints. J. Artif. Intell. Res. (JAIR) 27, 299–334.Google Scholar
Pelov, N. 2004. Semantics of Logic Programs with Aggregates. Ph.D. thesis, Katholieke Universiteit Leuven, Leuven, Belgium.Google Scholar
Pelov, N., Denecker, M. and Bruynooghe, M. 2007. Well-founded and stable semantics of logic programs with aggregates. Theory and Practice of Logic Programming 7, 3, 301–353.Google Scholar
Shen, Y., Wang, K., Eiter, T., Fink, M., Redl, C., Krennwallner, T. and Deng, J. 2014. FLP answer set semantics without circular justifications for general logic programs. Artif. Intell. 213, 1–41.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artif. Intell. 138, 1–2, 181–234.Google Scholar
Son, T. C. and Pontelli, E. 2007. A constructive semantic characterization of aggregates in answer set programming. Theory and Practice of Logic Programming 7, 3, 355–375.CrossRefGoogle Scholar
Supplementary material: PDF

Alviano and Leone supplementary material

Online Appendix

Download Alviano and Leone supplementary material(PDF)
PDF 198.5 KB