A Comparison of Two Approaches to Splitting Default Theories

AAAI 1997

TL;DR

This paper dives into two methods for simplifying complex nonmonotonic reasoning systems: Turner's "splitting" and Cholewinski's "stratification." The authors demonstrate that Turner's approach is essentially a specific, coarser version of Cholewinski's more general stratification, offering a clearer understanding of their relationship and potential for more efficient reasoning systems.

What Problem Does This Paper Address?

Nonmonotonic reasoning systems, like Reiter's default logic, are powerful tools for representing knowledge that can change or be updated. However, they suffer from significant computational expense, making it difficult to build practical AI systems. One promising avenue to tackle this is to "split" large knowledge bases into smaller, more manageable parts, allowing for local computations and then combining the results. This paper focuses on comparing two specific techniques for achieving this kind of splitting: Turner's "splitting" and Cholewinski's "stratification." The goal is to understand how they relate, whether one is a special case of the other, and how this understanding can lead to better implementations.

Methods

The paper meticulously compares two distinct methods for decomposing default theories:

  • Cholewinski's Stratification: This approach assigns a numerical "rank" to each default rule based on dependencies. If a default rule's consequent is used by another rule, the latter must have a higher rank. This creates ordered "strata" or layers of defaults, ensuring that rules are processed in a sensible order, preserving the original theory's extensions.
  • Turner's Splitting: This method involves identifying a "splitting set" of propositional atoms. The default theory is then divided into a "base" part (defaults operating solely on atoms within the splitting set) and a remaining part. The latter is then "partially evaluated" using a consistent extension of the base part. This process can be iterated using "splitting sequences."

The core of the paper's contribution lies in proving the formal relationship between these two methods. They demonstrate that Turner's splitting, when applied in a specific way, can be seen as a particular instance of Cholewinski's more general stratification.

Datasets

Not discussed in the paper. The paper focuses on theoretical comparison of formalisms rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Turner's Splitting is a Special Case of Stratification: This is the paper's central finding. It means that any theory that can be processed by Turner's splitting can also be handled by Cholewinski's stratification, but not necessarily vice-versa. Stratification offers a more granular way to decompose theories.
  • Preservation of Extensions: Both approaches are designed to split theories in a way that guarantees the resulting extensions are the same as those of the original, undivided theory. This is crucial for their practical utility.
  • Stratification's Finer Granularity: The paper highlights examples where stratification can separate defaults that Turner's splitting cannot, due to stricter conditions on how splitting sets are defined. This suggests stratification is more flexible in decomposing complex dependencies.
  • Practical Implications for Implementation: Understanding this relationship can help developers avoid reinventing the wheel and leverage the strengths of both approaches for building more efficient nonmonotonic reasoning systems.

Key Results

The paper presents several theorems and lemmas that formally establish the relationship between splitting and stratification. Key results include:

  • Lemma 5.1 & 5.4: Show how to construct a stratification function from a splitting set and a splitting sequence, respectively.
  • Lemma 5.2: Demonstrates the equivalence between Turner's partial evaluation and a concept in stratification related to "passing over" local extensions.
  • Corollary 5.3 & Theorem 5.5: Formally state that splitting and stratification, when properly defined, generate the same set of consistent extensions.
  • Example 5.6 & 5.7: Illustrate scenarios where stratification can achieve a finer decomposition than splitting.

Limitations and Future Work

  • Facts (W) Handling: The paper notes that while Cholewinski's stratification has a strict condition on facts (no propositional atoms in common with default consequents), Turner's approach is more flexible in this regard. The authors suggest this flexibility could be incorporated into stratification.
  • Generalization to Variants: The paper mentions that the concepts of splitting and stratification are applicable to various other nonmonotonic logics (e.g., Justified Default Logic, Constrained Default Logic, Rational Default Logic). Future work could explore how these ideas adapt to the specific "use" semantics of defaults in these variants.
  • Complexity Analysis: While the paper establishes the theoretical equivalence, a deeper dive into the computational complexity benefits of each approach, especially in practical implementations, could be a future direction. The authors reference Cholewinski's prior work on complexity and implementation, suggesting that further work in this area might not require re-inventing the wheel for splitting.

Summary updated

BibTeX
@inproceedings{1997comparison,
  title = {{A Comparison of Two Approaches to Splitting Default Theories}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1997},
}
Figure