Derivation Procedures for Extended Stable Models

Luís Moniz Pereira, Joaquim Nunes Aparício, José Júlio AlferesIJCAI 1991

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.

A derivation tree for the goal ~a based on a logic program with multiple rules.

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.

Derivation trees demonstrating the handling of circular dependencies between literals a and b.

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

BibTeX
@inproceedings{pereira1991derivation,
  author = {Luís Moniz Pereira and Joaquim Nunes Aparício and José Júlio Alferes},
  title = {{Derivation Procedures for Extended Stable Models}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1991},
}
Figure