Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-20T00:36:26.920Z Has data issue: false hasContentIssue false
  • English
  • Français

On Signings and the Well-Founded Semantics

Published online by Cambridge University Press:  20 April 2021

MICHAEL J. MAHER Open the ORCID record for MICHAEL J. MAHER [Opens in a new window]
MICHAEL J. MAHER*
Affiliation:
Reasoning Research Institute, Canberra, Australia (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

In this note, we use Kunen’s notion of a signing to establish two theorems about the well-founded semantics of logic programs, in the case where we are interested in only (say) the positive literals of a predicate p that are consequences of the program. The first theorem identifies a class of programs for which the well-founded and Fitting semantics coincide for the positive part of p. The second theorem shows that if a program has a signing, then computing the positive part of p under the well-founded semantics requires the computation of only one part of each predicate. This theorem suggests an analysis for query answering under the well-founded semantics. In the process of proving these results, we use an alternative formulation of the well-founded semantics of logic programs, which might be of independent interest.

Keywords

signingwell-founded semanticsquery optimization
Type
Technical Note
Information
Theory and Practice of Logic Programming , Volume 22 , Issue 1 , January 2022 , pp. 115 - 127
Copyright
© The Author(s), 2021. Published by Cambridge University Press

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.)

Footnotes

*

The author has an adjunct position at Griffith University and an honorary position at UNSW. He thanks the referees for comments that helped improve this paper.

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. Morgan Kaufmann, 89–148.CrossRefGoogle Scholar
Apt, K. R. and Bol, R. N. 1994. Logic programming and negation: A survey. Journal of Logic Programming 19/20, 9–71.CrossRefGoogle Scholar
Berman, K. A., Schlipf, J. S. and Franco, J. V. 1995. Computing well-founded semantics faster. In Logic Programming and Nonmonotonic Reasoning, Third International Conference, LPNMR 1995, Marek, V. W. and Nerode, A., Eds. Lecture Notes in Computer Science, vol. 928. Springer, 113–126.Google Scholar
Brass, S., Dix, J., Freitag, B. and Zukowski, U. 2001. Transformation-based bottom-up computation of the well-founded model. Theory and Practice of Logic Programming 1, 5, 497–538.CrossRefGoogle Scholar
Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. 2001. Introduction to Algorithms, 1st ed. The MIT Press and McGraw-Hill Book Company.Google Scholar
Drabent, W. and Martelli, M. 1991. Strict completion of logic programs. New Generation Computing 9, 1, 69–80.CrossRefGoogle Scholar
Dung, P. M. 1992. On the relations between stable and well-founded semantics of logic programs. Theoretical Computer Science 105, 1, 7–25.CrossRefGoogle Scholar
Fages, F. 1994. Consistency of Clark’s completion and existence of stable models. Methods of Logic in CS 1, 1, 51–60.Google Scholar
Fitting, M. 1985. A Kripke-Kleene semantics for logic programs. Journal of Logic Programming 2, 4, 295–312.CrossRefGoogle Scholar
Hitzler, P. and Wendt, M. 2002. The well-founded semantics is a stratified Fitting semantics. In KI 2002: Advances in Artificial Intelligence, 25th Annual German Conference on AI, KI 2002, Jarke, M., Koehler, J., and Lakemeyer, G., Eds. Lecture Notes in Computer Science, vol. 2479. Springer, 205–221.Google Scholar
Kemp, D. B., Ramamohanarao, K. and Stuckey, P. J. 1997. An efficient evaluation technique for non-stratified programs by transformation to explicitly locally stratified programs. Journal of Systems Integration 7, 3/4, 191–230.CrossRefGoogle Scholar
Kleene, S. C. 1952. Introduction to Metamathematics. Van Nostrand.Google Scholar
Kunen, K. 1989. Signed data dependencies in logic programs. Journal of Logic Programming 7, 3, 231–245.CrossRefGoogle Scholar
Maher, M. J. 2021. Defeasible reasoning via Datalog￢, forthcoming.CrossRefGoogle Scholar
Maher, M. J., Tachmazidis, I., Antoniou, G., Wade, S. and Cheng, L. 2020. Rethinking defeasible reasoning: A scalable approach. Theory and Practice of Logic Programming 20, 4, 552–586.CrossRefGoogle Scholar
Morishita, S. 1996. An extension of Van Gelder’s alternating fixpoint to magic programs. Journal of Computer and System Sciences 52, 3, 506–521.CrossRefGoogle Scholar
Turner, H. 1993. A monotonicity theorem for extended logic programs. In Proceedings of the Tenth International Conference on Logic Programming, 567–585.Google Scholar
Van Gelder, A. 1989. The alternating fixpoint of logic programs with negation. In Proceedings of the Eighth ACM Symposium on Principles of Database Systems, 1–10.Google Scholar
Van Gelder, A., Ross, K. A. and Schlipf, J. S. 1991. The well-founded semantics for general logic programs. Journal of the ACM 38, 3, 620–650.Google Scholar
Zaniolo, C., Yang, M., Interlandi, M., Das, A., Shkapsky, A. and Condie, T. 2017. Fixpoint semantics and optimization of recursive Datalog programs with aggregates. Theory and Practice of Logic Programming 17, 5–6, 1048–1065.CrossRefGoogle Scholar
Supplementary material: PDF

Maher supplementary material

Online Appendix

Download Maher supplementary material(PDF)
PDF 125.6 KB