Strong Equivalence for Epistemic Logic Programs Made Easy

Wolfgang Faber, Michael Morak, Stefan WoltranAAAI 2019 · DOI

Introduction

In the field of declarative programming, Answer Set Programming (ASP) has emerged as a powerful paradigm for solving knowledge-intensive search problems. However, standard ASP is limited when it comes to meta-reasoning—reasoning about the knowledge itself. Epistemic Logic Programs (ELPs) extend ASP by introducing epistemic operators (often denoted as K or epistemic negation not), which allow a program to reason across multiple possible answer sets (world views). This added expressivity allows for more nuanced modeling but significantly increases computational complexity.

A fundamental question in program development and optimization is whether two program fragments are interchangeable. This is captured by the notion of Strong Equivalence. Two programs are strongly equivalent if they can be swapped in any context without changing the resulting set of answer sets. While this property is well-understood for standard ASP, it has remained a complex and often abstract challenge for ELPs. This paper introduces a direct, model-theoretic characterization of strong equivalence for ELPs using a new construct called the SE-function.

The Challenge of Epistemic Reasoning

In standard ASP, strong equivalence is characterized by SE-models (based on the logic of Here-and-There). For ELPs, the problem is more difficult because the semantics of a program depends on the collection of all its answer sets, not just individual ones. Epistemic negation allows a rule to check if a literal is not known across all possible world views.

Previous attempts to define strong equivalence for ELPs often relied on complex translations into modal logics or were tied to specific, sometimes obsolete, semantic frameworks. Furthermore, the general reasoning task for ELPs (deciding the existence of a world view) is $\Sigma^P_3$-complete, which is two levels higher on the polynomial hierarchy than standard ASP. This led to the assumption that checking for strong equivalence would be similarly expensive.

The SE-function Approach

The authors propose a "direct" approach that builds upon the established SE-model framework but adapts it for the epistemic setting. Their core innovation is the SE-function.

1. Epistemic Reducts and Guesses

The framework utilizes the "reduct" approach. Given an ELP, one makes an "epistemic guess"—a hypothesis about which epistemic literals are true. This guess transforms the complex ELP into a standard ASP program (the epistemic reduct). If the answer sets of this reduct match the initial guess, the guess is considered a valid world view.

2. Characterizing Equivalence

The SE-function maps every possible epistemic guess to a set of SE-models. Crucially, the authors identify that not all guesses are relevant; they focus on "realizable" guesses—those that could potentially correspond to a valid set of answer sets under some context. The paper proves that two ELPs are strongly equivalent if and only if they share the exact same SE-function across all realizable guesses.

Complexity and Practical Insights

One of the most significant findings of the paper is the complexity of this check. Despite the high complexity of ELP reasoning in general, the authors prove that checking for strong equivalence is $coNP$-complete. This is the same complexity class as standard ASP, a surprising result that suggests optimizing ELP compilers by swapping equivalent code blocks is computationally feasible.

Syntactic Simplifications

Beyond the theoretical characterization, the paper provides practical tools for developers:

  • Tautology Identification: Concrete rules to identify rules that do not affect the program's semantics and can be safely removed.
  • Subsumption: Criteria to determine when one rule is logically "stronger" than another, allowing the redundant, weaker rule to be deleted.
  • Closed World Assumption (CWA): The authors demonstrate their framework's utility by comparing different ways of defining the CWA in ELPs, showing that seemingly similar formulations are not always strongly equivalent.

Conclusion

By introducing the SE-function, this paper provides a bridge between high-level epistemic theory and the practical needs of solver developers. It simplifies the verification of program transformations and establishes that the computational cost of ensuring modularity in ELPs is lower than previously feared. Future work remains in integrating these theoretical checks into automated optimization passes for state-of-the-art ELP solvers like clingo-epistemic and exploring "Uniform Equivalence"—equivalence under the addition of facts rather than arbitrary rules.

Summary updated

BibTeX
@inproceedings{faber2019strong,
  author = {Wolfgang Faber and Michael Morak and Stefan Woltran},
  title = {{Strong Equivalence for Epistemic Logic Programs Made Easy}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33012809},
}
Figure