TL;DR
This paper introduces a novel declarative semantics for logic programs, called "perfect model semantics," which unifies logic programming with four major non-monotonic reasoning formalisms: circumscription, closed world assumption, autoepistemic logic, and default logic. This work bridges a long-standing gap, offering a more principled understanding of logic programming and providing a procedural mechanism for complex reasoning tasks.
What Problem Does This Paper Address?
Artificial Intelligence (AI) relies heavily on reasoning, and two key areas are logic programming and non-monotonic reasoning. Logic programming offers a declarative way to represent knowledge and perform computations, while non-monotonic reasoning deals with situations where conclusions can be retracted as new information becomes available (e.g., "birds fly" is generally true, but penguins are an exception).
Historically, these fields have developed largely in parallel. Logic programming uses a form of negation called "negation as failure," which is inherently non-monotonic. However, the lack of a clear declarative semantics for this negation has made it difficult to fully realize the declarative programming ideal. On the other hand, non-monotonic reasoning formalisms, while powerful, often lacked efficient procedural implementations. This paper aims to bridge this divide by showing that a new declarative semantics for logic programs is equivalent to established non-monotonic reasoning frameworks.
Methods
The core of the paper introduces the perfect model semantics for logic programs. This semantics is built upon the concept of a perfect model, which is a minimal model that prioritizes the extensions of lower-priority predicates. The priority of predicates is determined by a dependency graph derived from the logic program. If a predicate B has a lower priority than A (denoted B < A), it means there's a path in the graph from B to A involving at least one negative edge. A model is considered "perfect" if it cannot be improved by enlarging higher-priority predicates at the expense of lower-priority ones.
For stratified logic programs (those whose dependency graph doesn't have cycles through negative edges), the paper proves that a unique perfect Herbrand model exists. This perfect model semantics is then shown to be equivalent to:
- Circumscription: Specifically, prioritized circumscription, where predicates are assigned priorities.
- Closed World Assumption (CWA): The paper shows equivalence with the Iterated Closed World Assumption (ICWA), a more sophisticated version of CWA.
- Autoepistemic Logic (AEL): A direct equivalence is established through a specific interpretation of logic program clauses.
- Default Logic: Equivalence is demonstrated by constructing a default theory associated with a logic program.
Additionally, the paper introduces SLS-resolution (Linear resolution with Selection function for Stratified programs) as a procedural mechanism that is sound and complete with respect to the perfect model semantics. For positive logic programs, SLS-resolution reduces to standard SLD-resolution.
Datasets
Not discussed in the paper. The paper focuses on theoretical formalisms and their equivalences, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Unification is Possible: The most significant insight is that a principled declarative semantics for logic programs (perfect model semantics) can be directly mapped to established non-monotonic reasoning formalisms. This suggests a deeper underlying unity between these fields.
- Prioritization is Key: The concept of predicate priorities, derived from the program's structure, is crucial for defining perfect models and establishing equivalences, particularly with circumscription.
- Procedural Power for Declarative Semantics: SLS-resolution provides a concrete computational method for reasoning under the perfect model semantics, offering a practical way to leverage these formalisms.
- Clark's Completion Limitations: The paper highlights that traditional approaches like Clark's predicate completion, while intuitive, are not general enough for broader non-monotonic reasoning and have certain drawbacks. Perfect model semantics offers a more robust alternative.
- Autoepistemic Logic's Built-in Prioritization: A fascinating point is that autoepistemic logic, unlike circumscription or CWA, doesn't require explicit prioritization to achieve equivalence with perfect model semantics, suggesting its inherent structure already captures this aspect.
Key Results
- Perfect Model Semantics Equivalence: The paper formally proves that the perfect model semantics of stratified logic programs is semantically equivalent to prioritized circumscription, Iterated Closed World Assumption, and a specific interpretation of autoepistemic logic and default logic.
- Unique Perfect Herbrand Model: Every stratified logic program has a unique perfect Herbrand model.
- SLS-Resolution Soundness and Completeness: SLS-resolution is proven to be sound and complete for stratified logic programs with respect to the perfect model semantics.
- SLDNF-Resolution as a Sound Inference Engine: The equivalence results imply that SLDNF-resolution (used in Prolog) can be used as a sound inference engine for certain forms of circumscription and autoepistemic logic.
Limitations and Future Work
- Stratified Programs: The core results are presented for stratified logic programs. The paper acknowledges that not all logic programs are stratified, and the behavior of perfect model semantics for non-stratified programs might differ.
- General Circumscription: While equivalence is shown for prioritized circumscription, the paper notes that general circumscription might require further investigation.
- Computational Complexity: While SLS-resolution provides a procedural mechanism, the computational complexity of perfect model semantics and its related formalisms is not deeply explored in this theoretical paper.
- Future Directions: The authors suggest that these results can contribute to a better understanding of the relationships between various non-monotonic reasoning forms and potentially lead to the discovery of deeper underlying principles. The ability to use SLDNF-resolution as a sound inference engine for these formalisms is also highlighted as a practical benefit.
Summary updated