Abstract
This paper introduces formal derivation procedures for determining goal satisfaction under Extended Stable Model (XSM) semantics. By bridging high-level logic programming theory with practical computation, the authors provide a framework to verify goals in multi-valued logic systems without exhaustive model generation. The proposed WFM and XSM derivation trees utilize contextual reasoning and specialized loop-handling rules to achieve sound and complete results across both skeptical and credulous reasoning frameworks.
Introduction
In logic programming, "negation as failure" typically assumes that unprovable statements are false. However, real-world reasoning often involves ambiguity or circularity, necessitating 3-valued logics like Well-Founded Semantics (WFS) and Extended Stable Models (XSMs). While WFS provides a skeptical core of truth, XSMs allow for the exploration of consistent "possible worlds" that build upon that core. The primary challenge addressed in this work is the lack of step-by-step derivation procedures—comparable to SLD-resolution in standard Prolog—specifically designed for these advanced semantics.
Methods
The authors propose two primary derivation structures: WFM-trees for the skeptical core and XSM-trees for credulous reasoning. These procedures rely on "contexts"—ordered sets of interpretations—to track assumptions and proofs during derivation.
Key technical innovations include rules (labeled D1.1 through D4) that manage recursive literals. In these tree-based proofs, the truth of a root node is determined by the nature of its leaf nodes, which may represent known facts or specific types of logical loops.
Key Insights and Ideas
A central insight is that the Well-Founded Model serves as the intersection of all Extended Stable Models. Consequently, any goal provable in the WFM is necessarily true in all XSMs.
The handling of cycles represents a significant advancement. In an XSM-tree, a branch can succeed even if it loops, provided there is a specific sequence of positive and negative literals between identical nodes. This "loop breaking" allows the system to resolve undefined states and explore specific stable worlds.
Furthermore, the authors demonstrate that these complex logical rules can be translated directly into a Prolog implementation, proving the framework's computational viability for actual software development.
Key Results
The authors provide formal proofs for the soundness and completeness of their procedures. If the procedure confirms a goal, it is guaranteed to be true in the model; conversely, if a goal is true in the model, the procedure will eventually find a proof. This unified framework successfully bridges skeptical and credulous logic programming within a single computational structure.
Limitations and Future Work
The current procedures assume the logic program has been "grounded," where all variables are replaced by constants. In large-scale applications, the resulting explosion of ground rules can become a significant bottleneck. Future research will focus on optimizing search strategies and addressing the grounding problem to enhance the efficiency of these derivation trees for general engineering use.
Summary updated