TL;DR
This paper investigates whether a standard technique for achieving "extensional" semantics in logic programming can be extended to handle negation in higher-order logic programs. While the technique works for stratified programs, it fails in the general case, highlighting the challenges of incorporating negation into these expressive programming paradigms.
What Problem Does This Paper Address?
Higher-order logic programming (HOLP) allows for predicates to be arguments to other predicates, making it a powerful paradigm for knowledge representation and reasoning. However, reasoning about HOLP programs can be complex. One way to simplify this is by achieving an "extensional semantics," where predicates are treated as sets of their arguments. This allows us to use standard set theory for analysis and leverage techniques from functional programming.
Previous work by Bezem proposed a method to achieve extensionality for positive HOLP programs by grounding the program and then analyzing its "ground instantiation." This paper tackles the question of whether this same technique, when combined with a three-valued semantics (which can handle undefined or unknown truth values, crucial for negation), can provide an extensional semantics for HOLP programs with negation. The core challenge is that negation can introduce complexities that might break the extensionality property.
Methods
The paper focuses on Bezem's approach, which involves:
- Ground Instantiation: Replacing variables in a program with all possible ground terms of the correct type. This transforms the higher-order program into an (potentially infinite) propositional-like program.
- Semantic Interpretation: Applying a standard semantics to this ground instantiation. The paper specifically investigates the well-founded semantics, a common three-valued semantics for logic programs with negation.
- Extensionality Check: Analyzing whether the resulting semantics treats predicates that are extensionally equivalent (i.e., true for the same arguments) as indistinguishable in the program's meaning.
The authors adapt Bezem's technique by using the well-founded semantics on the ground instantiation of higher-order logic programs with negation. They then formally define and check for extensionality.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Negation is Tricky: The paper's central finding is that simply applying Bezem's grounding technique with the well-founded semantics does not generally guarantee extensionality for higher-order logic programs with negation. This suggests that adding negation is not a straightforward extension of positive HOLP semantics.
- Stratification Saves the Day (Partially): For a specific class of programs called stratified programs, the well-founded adaptation does yield an extensional two-valued model. This reinforces the well-behaved nature of stratified programs, a property previously known for first-order logic.
- The Nature of Three-Valuedness: The authors hint that achieving a general three-valued extensional semantics for HOLP with negation might require strong, specific assumptions about how negation behaves, potentially going beyond standard interpretations.
Key Results
- Non-Extensionality: The paper provides an example of a higher-order logic program with negation that has a non-extensional well-founded model. This demonstrates that the technique fails in the general case.
- Extensionality for Stratified Programs: A theorem proves that for stratified higher-order logic programs, the well-founded model is indeed extensional and does not assign the "undefined" (0) truth value.
Limitations and Future Work
- General Three-Valued Semantics: The paper raises the open question of whether an alternative, general three-valued extensional semantics for HOLP with negation exists, suggesting it might require strong assumptions about negation.
- Locally Stratified Programs: The authors note that they have not yet been able to clarify whether locally stratified higher-order logic programs are well-behaved with respect to extensionality.
- Alternative Approaches: The paper briefly mentions ongoing work on alternative extensional three-valued semantics, such as those based on approximation fixpoint theory, as a promising avenue for future research.
Summary updated