On Reducing Parallel Circumscription

Li-Yan Yuan, Cheng Hui WangAAAI 1988

Abstract

In the field of artificial intelligence and knowledge representation, circumscription serves as a foundational formalism for non-monotonic reasoning—the ability to revise conclusions in the light of new information. However, the computational complexity of parallel circumscription, which allows certain predicates to vary during minimization, often necessitates the use of second-order logic. This paper by Yuan and Wang (1988) introduces a method to reduce parallel circumscription to basic circumscription. By employing a technique termed Z-resolution and identifying a class of "Z-conflict free" theories, the authors provide a structural shortcut that simplifies the calculation of common-sense logic without sacrificing expressive power.

Introduction

Human reasoning is inherently non-monotonic. We frequently make assumptions based on incomplete information—such as assuming a bird can fly—and retract those assumptions upon learning specific exceptions, such as the discovery that the bird in question is a penguin. In 1980, John McCarthy introduced circumscription to formalize this process by "minimizing" predicates, effectively enforcing the rule that we should assume as few things are true as possible given the evidence.

As the logic evolved to handle more complex scenarios, different forms of circumscription emerged:

  1. Basic Circumscription: Minimizing a set of predicates $P$ while keeping all other predicates fixed.
  2. Parallel Circumscription: Minimizing $P$ while allowing a separate set of predicates $Z$ to vary.
  3. Priority Circumscription: Minimizing $P$ according to a specific priority hierarchy.

While parallel circumscription is more expressive than the basic form, the "varying" predicates ($Z$) introduce significant mathematical complexity. This complexity often requires second-order logic formulas, making the reasoning process computationally expensive and difficult to implement in automated theorem provers. Yuan and Wang’s research addresses this bottleneck by seeking a way to transform the "hard" parallel version into the "easier" basic version.

Methodology: Z-Resolution and Conflict-Free Theories

The authors propose a reduction method centered on the structural properties of logical theories. The core of their approach involves two primary concepts: Z-resolution and Z-conflict free theories.

Z-Resolution

Inspired by Robinson’s standard resolution principle used in automated theorem proving, Z-resolution is a specialized algorithm designed to eliminate negative occurrences of varying predicates ($Z$). The objective is to transform the theory such that these predicates become "one-sided," appearing only positively within the logical rules. When a predicate is made one-sided, it no longer contributes to the complex variations that necessitate second-order logic during minimization.

Z-Conflict Free Theories

The authors identify that the difficulty of parallel circumscription is often a result of the structural interaction between predicates. They define a theory as "Z-conflict free" if the varying predicates do not possess recursive or circular dependencies that would prevent them from being resolved away. For these theories, the authors provide an iterative algorithm that takes an ordered list of $Z$ predicates and applies Z-resolution to "absorb" their complexity into the rest of the theory.

Key Insights

  • Structural Complexity: The paper demonstrates that the difficulty of parallel circumscription is not merely a function of the number of variables, but rather how those variables interact. If a theory is Z-conflict free, the perceived complexity is artificial and can be mathematically removed.
  • The Power of One-Sidedness: A critical observation is that if a varying predicate only appears on one side of a logical implication, it does not complicate the minimization of other predicates in the same way a fully varying predicate does.
  • Predicate Transformation: The authors suggest that even theories that are not initially Z-conflict free can sometimes be transformed into a conflict-free state by "flipping" or negating certain predicates, thereby expanding the applicability of their reduction method.

Results and Theoretical Impact

The primary contribution of the paper is Theorem 4.1, which proves that for any Z-conflict free theory, parallel circumscription is logically equivalent to the basic circumscription of a reduced theory. This result has significant implications for algorithmic efficiency. By reducing the problem to basic circumscription, researchers can utilize existing, more efficient tools—such as Przymusinski’s algorithm—to solve problems that were previously computationally prohibitive.

Furthermore, this work provides a vital theoretical bridge. It connects earlier work by Lifschitz, which reduced priority circumscription to parallel circumscription, with this new reduction from parallel to basic. Together, these findings create a clear hierarchy and a path toward simplifying the most complex forms of non-monotonic reasoning into their most manageable components.

Limitations and Future Directions

While the reduction method is powerful, it is not universal. The method is strictly applicable to Z-conflict free theories. Although the authors demonstrate that some theories can be transformed to meet this criteria, there remain "Z-conflict" cases where this specific shortcut cannot be applied.

Future research may focus on developing more sophisticated logical mappings to transform a wider array of conflicting theories into conflict-free ones. Additionally, while the mathematical foundation is robust, further work is needed to implement these algorithms in practical software environments and to quantitatively measure the speedup achieved in large-scale knowledge bases.

Summary updated

BibTeX
@inproceedings{yuan1988reducing,
  author = {Li-Yan Yuan and Cheng Hui Wang},
  title = {{On Reducing Parallel Circumscription}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure