Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T18:13:13.254Z Has data issue: false hasContentIssue false

On Signings and the Well-Founded Semantics

Published online by Cambridge University Press:  20 April 2021

MICHAEL J. MAHER*
Affiliation:
Reasoning Research Institute, Canberra, Australia (e-mail: michael.maher@reasoning.org.au)
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 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.

Information

Type
Technical Note
Copyright
© The Author(s), 2021. Published by Cambridge University Press
Supplementary material: PDF

Maher supplementary material

Online Appendix

Download Maher supplementary material(PDF)
PDF 125.6 KB