From Answer Set Logic Programming to Circumscription via Logic of GK

Fangzhen Lin, Yi Zhou

Abstract

This paper establishes a theoretical bridge between two major pillars of non-monotonic reasoning: Pearce's equilibrium logic (and Ferraris's propositional general logic programs) and classical circumscription. By embedding these formalisms into Lin and Shoham’s logic of GK—a non-monotonic modal logic that encompasses both Reiter’s default logic and Moore’s autoepistemic logic—the authors derive a mapping from general logic programs to circumscription. This mapping facilitates the verification of strong equivalence between logic programs using classical logic and extends the semantics of general logic programs to the first-order case.

Introduction

In the field of Knowledge Representation (KR), non-monotonic reasoning allows AI systems to make common-sense assumptions that can be retracted when new information arrives. Two dominant but historically distinct formalisms for this are Answer Set Programming (ASP) and Circumscription. While ASP is widely utilized for solving complex combinatorial problems through stable model semantics, Circumscription provides a classical logic-based approach to minimizing predicates.

Historically, these two systems were linked only for specific, restricted classes of logic programs. However, recent advancements by Ferraris expanded the definition of logic programs to include arbitrary propositional formulas. This paper addresses a fundamental challenge: creating a generalized mapping that translates these complex, modern logic programs into the well-understood language of Circumscription. By doing so, researchers can leverage the extensive theoretical tools and solvers developed for Circumscription to analyze modern ASP.

The Intermediary: The Logic of GK

The core of this unification is the Logic of GK (Ground Logics of Knowledge), introduced by Lin and Shoham. The Logic of GK is a modal logic characterized by two primary operators:

  • K (Knowledge): Representing what is known.
  • A (Justified Assumptions): Representing what is assumed.

The authors utilize GK as a "universal translator." Because GK has already been shown to simulate other major non-monotonic systems like Default Logic and Autoepistemic Logic, proving that it can also capture Ferraris’s general logic programs effectively unifies several disparate branches of AI logic.

Methodology: A Three-Step Translation

The authors propose a systematic mapping process to bridge the gap between ASP and Circumscription:

  1. Translation to GK ($F_{GK}$): The authors define a mapping that converts a general logic program into a formula within the Logic of GK. They demonstrate that the "reduct"—the mathematical mechanism used to define stable models in ASP—can be elegantly expressed through the interaction between the $K$ and $A$ operators.
  2. GK to Circumscription: Building on existing proofs that GK can capture Circumscription, the authors show how these GK formulas can be transformed into circumscribed classical formulas.
  3. First-Order Extension: The mapping is extended from propositional logic to first-order logic (logic involving variables and quantifiers). This extension assumes a finite domain and unique names, providing a classical foundation for first-order ASP.

Key Insights and Theoretical Results

Unification of Semantics

The research proves that a set of atoms is a stable model of a program if and only if it corresponds to a "GK model" of the translated formula. This confirms that the stable model semantics for first-order logic programs is essentially equivalent to a specific form of first-order circumscription. This result provides a rigorous classical logic foundation for the semantics of modern ASP solvers.

Simplifying Strong Equivalence

One of the most practical contributions of this work concerns "strong equivalence." Two logic programs are strongly equivalent if they behave identically when embedded in any larger program. Previously, checking this required specialized non-classical logics. The authors demonstrate that once programs are translated into the GK framework, strong equivalence can be verified using standard classical logic tautologies.

Complexity and Proofs

The paper provides formal proofs (Theorems 2, 3, and 4) establishing the equivalence between these systems. While the problem of deciding strong equivalence is shown to be co-NP complete, the reduction to classical propositional logic offers a clear path for verification using existing SAT-based tools.

Limitations and Future Directions

While the paper provides a robust mathematical bridge, certain limitations remain:

  • Domain Assumptions: The first-order mapping currently relies on finite domains and unique name assumptions. Extending this framework to infinite domains or languages with complex function symbols remains an open challenge.
  • Implementation: The work is primarily theoretical. While it provides the mapping, it does not introduce a specific solver or engine to perform these translations for industrial-scale ASP problems.

Conclusion

By positioning the Logic of GK as a central hub, this research successfully unifies two of the most influential frameworks in non-monotonic reasoning. The ability to translate general logic programs into circumscription not only deepens our theoretical understanding of stable models but also provides practical methodologies for program verification and the expansion of ASP into first-order logic.

Summary updated

Abstract

We first embed Pearce's equilibrium logic and Ferraris's propositional general logic programs in Lin and Shoham's logic of GK, a nonmonotonic modal logic that has been shown to include as special cases both Reiter's default logic in the propositional case and Moore's autoepistemic logic. From this embedding, we obtain a mapping from Ferraris's propositional general logic programs to circumscription, and show that this mapping can be used to check the strong equivalence between two propositional logic programs in classical logic. We also show that Ferraris's propositional general logic programs can be extended to the first-order case, and our mapping from Ferraris's propositional general logic programs to circumscription can be extended to the first-order case as well to provide a semantics for these first-order general logic programs.
BibTeX
@inproceedings{lin2007from,
  author = {Fangzhen Lin and Yi Zhou},
  title = {{From Answer Set Logic Programming to Circumscription via Logic of GK}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
  url = {https://openreview.net/forum?id=Hybf6NzuWr},
}
Figure