Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-18T13:46:04.841Z Has data issue: false hasContentIssue false
  • English
  • Français

Functional ASP with Intensional Sets: Application to Gelfond-Zhang Aggregates

Published online by Cambridge University Press:  10 August 2018

PEDRO CABALAR ,
JORGE FANDINNO Open the ORCID record for JORGE FANDINNO [Opens in a new window] ,
LUIS FARIÑAS DEL CERRO  and
DAVID PEARCE
PEDRO CABALAR
Affiliation:
Department of Computer Science, University of Corunna, Corunna, Spain (e-mail: [email protected])
JORGE FANDINNO
Affiliation:
IRIT, Université de Toulouse, CNRS, Toulouse, France (e-mails: [email protected], [email protected])
LUIS FARIÑAS DEL CERRO
Affiliation:
IRIT, Université de Toulouse, CNRS, Toulouse, France (e-mails: [email protected], [email protected])
DAVID PEARCE
Affiliation:
Universidad Politécnica de Madrid, Madrid, Spain (e-mail: [email protected])
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

In this paper, we propose a variant of Answer Set Programming (ASP) with evaluable functions that extends their application to sets of objects, something that allows a fully logical treatment of aggregates. Formally, we start from the syntax of First Order Logic with equality and the semantics of Quantified Equilibrium Logic with evaluable functions (${\rm QEL}^=_{\cal F}$). Then, we proceed to incorporate a new kind of logical term, intensional set (a construct commonly used to denote the set of objects characterised by a given formula), and to extend ${\rm QEL}^=_{\cal F}$ semantics for this new type of expression. In our extended approach, intensional sets can be arbitrarily used as predicate or function arguments or even nested inside other intensional sets, just as regular first-order logical terms. As a result, aggregates can be naturally formed by the application of some evaluable function (count, sum, maximum, etc) to a set of objects expressed as an intensional set. This approach has several advantages. First, while other semantics for aggregates depend on some syntactic transformation (either via a reduct or a formula translation), the ${\rm QEL}^=_{\cal F}$ interpretation treats them as regular evaluable functions, providing a compositional semantics and avoiding any kind of syntactic restriction. Second, aggregates can be explicitly defined now within the logical language by the simple addition of formulas that fix their meaning in terms of multiple applications of some (commutative and associative) binary operation. For instance, we can use recursive rules to define sum in terms of integer addition. Last, but not least, we prove that the semantics we obtain for aggregates coincides with the one defined by Gelfond and Zhang for the ${\cal A}\mathit{log}$ language, when we restrict to that syntactic fragment.

Keywords

Answer Set ProgrammingEquilibrium LogicPartial FunctionsAggregates
Type
Original Article
Information
Theory and Practice of Logic Programming , Volume 18 , Special Issue 3-4: 34th International Conference on Logic Programming , July 2018 , pp. 390 - 405
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

*Partially supported by MINECO, Spain, grant TIC2017-84453-P, Xunta de Galicia, Spain (GPC ED431B 2016/035 and 2016-2019 ED431G/01, CITIC). The second author is funded by the Centre International de Mathématiques et d'Informatique de Toulouse (CIMI) through contract ANR-11-LABEX-0040-CIMI within the program ANR-11-IDEX-0002-02. The fourth author is supported by UPM project RP151046021.

References

Balduccini, M. 2013. ASP with non-herbrand partial functions: a language and system for practical use. TPLP 13, 4–5, 547–561.Google Scholar
Baral, C. 2003. Knowledge representation, reasoning and declarative problem solving. Cambridge university press.Google Scholar
Bartholomew, M. and Lee, J. 2014. Stable models of multi-valued formulas: Partial versus total functions. In Principles of Knowledge Representation and Reasoning: Proceedings of the Fourteenth International Conference, KR 2014, Vienna, Austria, July 20-24, 2014, Baral, C., Giacomo, G. D., and Eiter, T., Eds. AAAI Press.Google Scholar
Beeri, C., Naqvi, S. A., Shmueli, O., and Tsur, S. 1991. Set constructors in a logic database language. J. Log. Program. 10, 3&4, 181–232.Google Scholar
Cabalar, P. 2011. Functional answer set programming. Theory and Practice of Logic Programming 11, 2–3, 203–233.Google Scholar
Cabalar, P. 2013. Setting the stage for ASP functions. ALP Newsletter.Google Scholar
Cabalar, P., Fandinno, J., Schaub, T., and Schellhorn, S. 2017. Gelfond-Zhang aggregates as propositional formulas. In Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3-6, 2017, Proceedings, Balduccini, M. and Janhunen, T., Eds. LNCS, vol. 10377. Springer, 117–131.Google Scholar
Cabalar, P., Fariñas del Cerro, L., Pearce, D., and Valverde, A. 2014. A free logic for stable models with partial intensional functions. In Proc. of the 14th European Conference on Logics in Artificial Intelligence (JELIA'14). Lecture Notes in Artificial Intelligence, vol. 8761. 340–354.Google Scholar
Cabalar, P., Kaminski, R., Ostrowski, M., and Schaub, T. 2016. An ASP semantics for default reasoning with constraints. In Proc. of the 25th Intl. Joint Conference on Artificial Intelligence (IJCAI'16), New York, USA, July 9-15th, 2016, Kambhampati, S., Ed. 1015–1021.Google Scholar
Dovier, A., Omodeo, E. G., Pontelli, E., and Rossi, G. 1991. {log}: A logic programming language with finite sets. In Logic Programming, Proceedings of the Eigth International Conference, Paris, France, June 24-28, 1991, Furukawa, K., Ed. MIT Press, 111–124.Google Scholar
Dovier, A., Pontelli, E., and Rossi, G. 2003. Intensional sets in CLP. In Logic Programming, 19th International Conference, ICLP 2003, Mumbai, India, December 9-13, 2003, Proceedings, Palamidessi, C., Ed. Lecture Notes in Computer Science, vol. 2916. Springer, 284–299.Google Scholar
Faber, W., Pfeifer, G., and Leone, N. 2011. Semantics and complexity of recursive aggregates in answer set programming. Artificial Intelligence 175, 1, 278–298.Google Scholar
Ferraris, P. 2011. Logic programs with propositional connectives and aggregates. ACM Transactions on Computational Logic 12, 4, 25.Google Scholar
Ferraris, P. and Lifschitz, V. 2010. On the stable model semantics of first-order formulas with aggregates. In Proceedings of the 2010 Workshop on Nonmonotonic Reasoning.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
Harrison, A., Lifschitz, V., and Raju, D. 2017. Program completion in the input language of GRINGO. TPLP 17, 5–6, 855–871.Google Scholar
Heyting, A. 1930. Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, 42–56.Google Scholar
Kuper, G. M. 1990. Logic programming with sets. J. Comput. Syst. Sci. 41, 1, 44–64.Google Scholar
Lee, J. and Meng, Y. 2009. On reductive semantics of aggregates in answer set programming. In Logic Programming and Nonmonotonic Reasoning, Erdem, E., Lin, F., and Schaub, T., Eds. Springer Berlin Heidelberg, Berlin, Heidelberg, 182–195.Google Scholar
Lin, F. and Wang, Y. 2008. Answer set programming with functions. In Proc. of the 11th Intl. Conf. on Principles of Knowledge Representation and Reasoning (KR'08).Google Scholar
Pearce, D. 1996. A new logical characterisation of stable models and answer sets. In Non monotonic extensions of logic programming. Proc. NMELP'96. (LNAI 1216). Springer-Verlag.Google Scholar
Pearce, D. and Valverde, A. 2004. Towards a first order equilibrium logic for nonmonotonic reasoning. In Logics in Artificial Intelligence, 9th European Conference, JELIA 2004, Lisbon, Portugal, September 27-30, 2004, Proceedings, Alferes, J. J. and Leite, J. A., Eds. Lecture Notes in Computer Science, vol. 3229. Springer, 147–160.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
Simons, P., Niemelä, I., and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 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.Google Scholar
Supplementary material: PDF

Cabalar et al. supplementary material

Cabalar et al. supplementary material 1

Download Cabalar et al. supplementary material(PDF)
PDF 363.4 KB