Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-23T19:26:39.941Z Has data issue: false hasContentIssue false
  • English
  • Français

Functional answer set programming

Published online by Cambridge University Press:  04 February 2011

PEDRO CABALAR
PEDRO CABALAR*
Affiliation:
Department of Computer Science, University of Corunna, Corunna, Spain (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this paper we propose an extension of Answer Set Programming (ASP) to deal with (possibly partial) evaluable functions. To this aim, we start from the most general logical counterpart of ASP, Quantified Equilibrium Logic (QEL), and propose a variant QEL=ℱ where the set of functions is partitioned into Herbrand functions (or constructors) and evaluable functions (or operations). We show how this extension has a direct connection to Scott's Logic of Existence, and introduce several useful derived operators, some of them directly borrowed from Scott's formalisation. Using this general framework for arbitrary theories, we proceed to focus on a syntactic subclass that corresponds to normal logic programs with evaluable functions and equality. We provide a translation of this class into function-free normal programs and consider a safety condition so that the resulting program is also safe, under the usual meaning in ASP. Finally, we also establish a formal comparison to Lin and Wang's approach (FASP) dealing with evaluable total functions.

Keywords

answer set programmingequilibrium logicpartial functionsfunctional logic programming
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 2-3: The 24th International Conference on Logic Programming (ICLP 2008) , March 2011 , pp. 203 - 233
Copyright
Copyright © Cambridge University Press 2011

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

Barringer, H., Cheng, H. and Jones, C. B. 1984. A logic covering undefinedness in program proofs. Acta Informatica 21, 251–269.CrossRefGoogle Scholar
Bonatti, P. A. 2004. Reasoning with infinite stable models. Artificial Intelligence 156, 75–111.CrossRefGoogle Scholar
Cabalar, P. 2005. A functional action language front-end [online]. In Presentation at the 3rd Workshop on Answer Set Programming (ASP'05). Accessed January 2011. URL: http://www.dc.fi.udc.es/ai/~cabalar/asp05_C.pdfGoogle Scholar
Cabalar, P. 2008. Partial functions and equality in answer set programming. In Proc. of the 24th International Conference on Logic Programming, ICLP 2008 (Udine, Italy, December 9–13 2008) de la Banda, M. G. and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer, 392–456.Google Scholar
Cabalar, P. 2009. Existential quantifiers in the rule body. In Proc. of the 23rd Workshop on (Constraint) Logic Programming (WLP'09). Geske, U. and Wolf, A., Eds. Universitätsverlag Potsdam, 59–74Google Scholar
Cabalar, P. and Lorenzo, D. 2004. Logic programs with functions and default values. In Proc. of the 9th European Conference on Logics in AI (JELIA'04). Alferes, J. J. and Leite, J., Eds. Lecture Notes in Computer Science, vol. 3229. Springer-Verlag, 294–306.Google Scholar
Ferraris, P., Lee, J. and Lifschitz, V. 2007. A new perspective on stable models. In Proc. of the International Joint Conference on Artificial Intelligence (IJCAI'07). Veloso, M. M., Ed. Morgan Kunfmann, 372–379.Google Scholar
Gebser, M., Schaub, T. and Thiele, S. 2007. GrinGo : A new grounder for answer set programming. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07). Baral, C., Brewka, G. and Schlipf, J., Eds. Lecture Notes in Computer Science, vol. 4483. Springer, 266–271.CrossRefGoogle Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference on Logic Programming. Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, 1070–1080.Google Scholar
Gelfond, M. and Lifschitz, V. 1993. Representing action and change by logic programs. Journal of Logic Programming 17, 301–321.CrossRefGoogle Scholar
González-Moreno, J. C., Hortalá-González, T., López-Fraguas, F. and Rodríguez-Artalejo, M. 1999. An approach to declarative programming based on a rewriting logic. Journal of Logic Programming 40, 1, 47–87.CrossRefGoogle Scholar
Hanus, M. 1994. The integration of functions into logic programming: From theory to practice. Journal of Logic Programming 19, 20, 583–628.CrossRefGoogle Scholar
Hanus, M. 2007. Multi-paradigm declarative languages. In Proc. of the International Conference on Logic Programming (ICLP 2007). Dahl, V. and Niemelä, I., Eds. Lecture Notes in Computer Science, vol. 4670. Springer, 45–75.Google Scholar
Heyting, A. 1930. Die formalen Regeln der intuitionistischen Logik. Sitzungsberichte der Preussischen Akademie der Wissenschaften, Physikalisch-mathematische Klasse, 42–56.Google Scholar
Heyting, A. 1956. Intuitionism. An Introduction. North-Holland.Google Scholar
Lee, J. and Palla, R. 2009. System F2LP – Computing answer sets of first-order formulas. In Proc. of the 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09). Erdem, E., Lin, F. and Schaub, T., Eds. Lecture Notes in Artificial Intelligence 5753. Springer-Verlag, 515–521.CrossRefGoogle Scholar
Leone, N., Pfeifer, G., Faber, W., Eiter, T., Gottlob, G., Perri, S. and Scarcello, F. 2006. The DLV system for knowledge representation and reasoning. ACM Transactions on Computational Logic 7, 3, 499–562.CrossRefGoogle Scholar
Lifschitz, V., Pearce, D. and Valverde, A. 2007. A characterization of strong equivalence for logic programs with variables. In Proc. of the 9th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'07). Baral, C., Brewka, G. and Schlipf, J. S., Eds. Springer-Verlag, 188–200.CrossRefGoogle Scholar
Lin, F. and Wang, Y. 2008. Answer set programming with functions. In Proc. of the 11th International Conference on Principles of Knowledge Representation and Reasoning (KR'08). Brewka, G. and Lang, J., Eds. AAAI Press, 454–465Google Scholar
Marek, V. and Truszczyński, M. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm: a 25-Year Perspective. Apt, K. R., Marek, V. W., Truszczynski, M. and Warren, D. S., Eds. Springer-Verlag, 169–181.Google Scholar
McCarthy, J. 1980. Circumscription: A form of non-monotonic reasoning. Artificial Intelligence 13, 27–39.CrossRefGoogle Scholar
Naish, L. 1991. Adding equations to NU-Prolog. In Proc. of the 3rd International Symposium on Programming Language Implementation and Logic Programming. Maluszynski, J. and Wirsing, M., Eds. Lecture Notes in Computer Science, vol. 528. Springer-Verlag, 15–26.CrossRefGoogle 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). Dix, J., Pereira, L. M. and Przymusinski, T. C., Eds. Springer-Verlag.Google Scholar
Pearce, D. and Valverde, A. 2004. Towards a first order equilibrium logic for nonmonotonic reasoning. In Proc. of the 9th European Conference on Logics in AI (JELIA'04). Alferes, J. J. and Leite, J., Eds. Springer-Verlag, 147–160.Google Scholar
Pearce, D. and Valverde, A. 2008. Quantified equilibrium logic and foundations for answer set programs. In Proc. of the 24th International Conference on Logic Programming, ICLP 2008, (Udine, Italy, December 9–13 2008). de la Banda, M. G. and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer, 546–560.Google Scholar
Rodríguez-Artalejo, M. 2001. Functional and constraint logic programming. In Revised Lectures of the International Summer School CCL'99. Hubert, C., Claude, M. and Ralf, T., Eds. Lecture Notes in Computer Science, vol. 2002. Springer, 202–270.Google Scholar
Rouveirol, C. 1994. Flattening and saturation: Two representation changes for generalization. Machine Learning 14, 1, 219–232.CrossRefGoogle Scholar
Scott, D. 1979. Identity and existence in intuitionistic logic. Lecture Notes in Mathematics 753, 660–696.CrossRefGoogle Scholar
Šimkus, M. and Eiter, T. 2007. Decidable non-monotonic disjunctive logic programs with function symbols. In Proc. of the 14th International Conference on Logic for Programming, Artificial Intelligence. Dershowitz, N. and Voronkov, A., Eds. Lecture Notes in Computer Science, vol. 4790. Springer-Verlag, 514–530.Google Scholar
Syrjänen, T. 2001. Omega-restricted logic programs. In Proc. of the 6th International Conference on Logic Programming and Nonmonotonic Reasoning. Eiter, T., Faber, W. and Truszczynski, M., Eds. Lecture Notes in Computer Science, vol. 2173. Springer-Verlag, 267–279.Google Scholar
Syrjänen, T. 2007. Lparse 1.0 user's manual [online]. Acessed January 2011. URL: http://www.tcs.hut.fi/Software/smodels/lparse.psGoogle Scholar