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

The intricacies of three-valued extensional semantics for higher-order logic programs

Published online by Cambridge University Press:  23 August 2017

PANOS RONDOGIANNIS  and
IOANNA SYMEONIDOU
PANOS RONDOGIANNIS
Affiliation:
National and Kapodistrian University of Athens, Athens, Greece (e-mail: [email protected], [email protected])
IOANNA SYMEONIDOU
Affiliation:
National and Kapodistrian University of Athens, Athens, Greece (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

M. Bezem defined an extensional semantics for positive higher-order logic programs. Recently, it was demonstrated by Rondogiannis and Symeonidou that Bezem's technique can be extended to higher-order logic programs with negation, retaining its extensional properties, provided that it is interpreted under a logic with an infinite number of truth values. Rondogiannis and Symeonidou also demonstrated that Bezem's technique, when extended under the stable model semantics, does not in general lead to extensional stable models. In this paper, we consider the problem of extending Bezem's technique under the well-founded semantics. We demonstrate that the well-founded extension fails to retain extensionality in the general case. On the positive side, we demonstrate that for stratified higher-order logic programs, extensionality is indeed achieved. We analyze the reasons of the failure of extensionality in the general case, arguing that a three-valued setting cannot distinguish between certain predicates that appear to have a different behaviour inside a program context, but which happen to be identical as three-valued relations.

Keywords

Extensional higher-order logic programmingNegation in logic programming
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 17 , Special Issue 5-6: 33rd International Conference on Logic Programming , September 2017 , pp. 974 - 991
Copyright
Copyright © Cambridge University Press 2017 

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

Apt, K. R., Blair, H. A. and Walker, A. 1988. Towards a theory of declarative knowledge. In Foundations of Deductive Databases and Logic Programming, Minker, J., Ed. Morgan Kaufmann, 89–148.CrossRefGoogle Scholar
Bezem, M. 1999. Extensionality of simply typed logic programs. In Proc. Logic Programming: The 1999 International Conference, Las Cruces, New Mexico, USA, November 29–December 4, 1999, Schreye, D. D., Ed. MIT Press, 395–410.Google Scholar
Bezem, M. 2001. An improved extensionality criterion for higher-order logic programs. In Proc. of Computer Science Logic, 15th International Workshop, CSL 2001. 10th Annual Conference of the EACSL, Paris, France, September 10–13, 2001, Fribourg, L., Ed. Lecture Notes in Computer Science, vol. 2142. Springer, 203–216.Google Scholar
Bloom, S. L. and Ésik, Z. 1993. Iteration Theories - The Equational Logic of Iterative Processes. EATCS Monographs on Theoretical Computer Science. Springer.Google Scholar
Carayol, A. and Ésik, Z. 2016. An analysis of the equational properties of the well-founded fixed point. In Proc. of Principles of Knowledge Representation and Reasoning: Proceedings of the 15th International Conference, KR 2016, Cape Town, South Africa, April 25–29, 2016, Baral, C., Delgrande, J. P. and Wolter, F., Eds. AAAI Press, 533–536.Google Scholar
Charalambidis, A., Ésik, Z. and Rondogiannis, P. 2014. Minimum model semantics for extensional higher-order logic programming with negation. Theory and Practice of Logic Programming 14, 4–5, 725–737.CrossRefGoogle Scholar
Charalambidis, A., Handjopoulos, K., Rondogiannis, P. and Wadge, W. W. 2013. Extensional higher-order logic programming. ACM Transaction on Computational Logic 14, 3, 21.Google Scholar
Charalambidis, A., Rondogiannis, P. and Symeonidou, I. 2017. Equivalence of two fixed-point semantics for definitional higher-order logic programs. Theoretical Computer Science 668, 27–42.CrossRefGoogle Scholar
Chen, W., Kifer, M. and Warren, D. S. 1993. HILOG: A foundation for higher-order logic programming. Journal of Logic Programming 15, 3, 187–230.CrossRefGoogle Scholar
Chomicki, J. 2003. Preference formulas in relational queries. ACM Transactions on Database Systems 28, 4, 427–466.CrossRefGoogle Scholar
Denecker, M., Bruynooghe, M. and Vennekens, J. 2012. Approximation fixpoint theory and the semantics of logic and answers set programs. In Correct Reasoning - Essays on Logic-Based AI in Honour of Vladimir Lifschitz, Erdem, E., Lee, J., Lierler, Y. and Pearce, D., Eds. Lecture Notes in Computer Science, vol. 7265. Springer, 178–194.CrossRefGoogle Scholar
Ésik, Z. 2015. Equational properties of stratified least fixed points (extended abstract). In Proc. of Logic, Language, Information, and Computation - 22nd International Workshop, WoLLIC 2015, Bloomington, IN, USA, July 20–23, 2015, de Paiva, V., de Queiroz, R. J. G. B., Moss, L. S., Leivant, D., and de Oliveira, A. G., Eds. Lecture Notes in Computer Science vol. 9160. Springer, 174–188.Google Scholar
Gelder, A. V. 1989. Negation as failure using tight derivations for general logic programs. Journal of Logic Programming 6, 1&2, 109–133.CrossRefGoogle Scholar
Gelder, A. V., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of ACM 38, 3, 620–650.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. In Proc. of the 5th International Conference and Symposium Logic Programming, Seattle, Washington, August 15–19, 1988 (2 Volumes), Kowalski, R. A. and Bowen, K. A., Eds. MIT Press, 1070–1080.Google Scholar
Kountouriotis, V., Rondogiannis, P. and Wadge, W. W. 2005. Extensional higher-order datalog. In Short Paper Proc. of the 12th International Conference on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), 1–5.Google Scholar
Lloyd, J. W. 1987. Foundations of Logic Programming. Springer Verlag.CrossRefGoogle Scholar
Miller, D. and Nadathur, G. 2012. Programming with Higher-Order Logic, 1st ed. Cambridge University Press, New York, NY, USA.CrossRefGoogle Scholar
Przymusinska, H. and Przymusinski, T. 1990. Semantic issues in deductive databases and logic programs. In Formal Techniques in Artificial Intelligence. North-Holland, 321–367.Google Scholar
Przymusinski, T. C. 1988. On the declarative semantics of deductive databases and logic programs. Foundations of Deductive Databases and Logic Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 193–216.CrossRefGoogle Scholar
Rondogiannis, P. and Symeonidou, I. 2016. Extensional semantics for higher-order logic programs with negation. In Proc. of Logics in Artificial Intelligence - 15th European Conference, JELIA 2016, Larnaca, Cyprus, November 9–11, 2016, Michael, L. and Kakas, A. C., Eds. Lecture Notes in Computer Science, vol. 10021, 447–462.Google Scholar
Rondogiannis, P. and Symeonidou, I. 2017. Extensional semantics for higher-order logic programs with negation. CoRR abs/1701.08622.CrossRefGoogle Scholar
Rondogiannis, P. and Wadge, W. W. 2005. Minimum model semantics for logic programs with negation-as-failure. ACM Transactions on Computational Logic 6, 2, 441–467.CrossRefGoogle Scholar
Wadge, W. W. 1991. Higher-order horn logic programming. In Proc. the 1991 International Symposium on Logic Programming, Larnaca, Cyprus, San Diego, California, USA, Oct. 28–Nov 1, 1991, Saraswat, V. A. and Ueda, K., Eds. MIT Press, 289–303.Google Scholar
Supplementary material: PDF

Rondogiannis and Symeonidou supplementary material

Online Appendix

Download Rondogiannis and Symeonidou supplementary material(PDF)
PDF 144.5 KB