Witnesses for Answer Sets of Basic Logic Programs

Yisong Wang, Xianglong Wang, Zhongtao Xie, Thomas EiterIJCAI 2025 · DOI

Introduction

Answer Set Programming (ASP) has emerged as a dominant paradigm in symbolic AI for solving complex combinatorial problems, including scheduling, planning, and automated diagnosis. As the field matures, ASP programs increasingly incorporate "c-atoms" (abstract constraint atoms), such as aggregates and weight constraints, to handle high-level logic efficiently. However, this increased expressive power comes at the cost of transparency. Understanding why a specific atom is included in an answer set—a prerequisite for debugging and trust—remains a significant challenge.

Presented at IJCAI-25, the paper "Witnesses for Answer Sets of Basic Logic Programs" addresses this gap by introducing a formal framework for generating "witnesses." These witnesses serve as minimal, sufficient justifications that explain the presence of specific atoms in a solution without relying on circular reasoning.

The Challenge: Complexity and Circularity

Standard ASP solvers are often treated as "black boxes." When a program outputs a solution, developers frequently need to trace the specific rules and constraints that forced a particular decision. This task is complicated by two primary factors:

  1. C-atoms: High-level constructs (e.g., "at least two of these three conditions must be met") are powerful but obscure the underlying logical dependencies, making them harder to trace than simple definite clauses.
  2. Vicious Circles: Some semantics for logic programs allow for circular justifications (e.g., Atom A is true because Atom B is true, and vice versa). To provide meaningful explanations, the authors focus on SPT-answer sets, which are specifically designed to exclude such circularity, ensuring that every conclusion has a grounded, non-circular basis.

The Minimal Reduct and SPT-Semantics

The authors propose a three-tiered approach to building explanations, beginning with the Minimal Reduct (MR). The MR is a method for simplifying a logic program relative to a specific solution. By stripping away irrelevant rules and decomposing complex c-atoms into their essential components, the MR provides a clean logical foundation for constructing proofs.

One of the paper's core theoretical contributions is a Characterization Theorem, which proves that an interpretation is an SPT-answer set if and only if it is the least model of its minimal reduct. This provides a simplified, more intuitive way to conceptualize SPT semantics in the context of explainability.

CA-Resolution: A Proof System for C-Atoms

Traditional resolution—the process of deriving new facts from existing ones—is insufficient for programs containing complex constraints. To bridge this gap, the authors introduce CA-resolution, an extension of standard resolution designed to handle c-atoms directly.

The authors demonstrate that CA-resolution is both sound (it does not derive false conclusions) and complete for SPT-semantics. Specifically, they prove that every atom in a valid SPT-answer set possesses a sound CA-resolution proof originating from the minimal reduct. This establishes a formal link between automated reasoning and step-by-step human-understandable justifications.

Generating Witnesses

The framework defines two distinct types of justifications, termed "witnesses":

  • $\alpha$-witness: This explains why a group of atoms is true, structured as a directed acyclic graph (DAG) of dependencies. It provides a holistic view of the reasoning chain.
  • $\beta$-witness: A more refined version that focuses on justifying a single atom. This is particularly useful for human developers who need to debug specific, isolated conclusions within a large program.

To make this framework actionable, the paper introduces algorithms—MinWitness and MinBetaWitness—designed to extract the minimal subprograms that serve as the "smoking gun" for any given conclusion. Compared to previous methods like r-justifications, these witnesses are more selective, aiming to reduce the cognitive load on the user by providing only the most essential information.

Conclusion and Future Work

While the current contribution is primarily theoretical, it lays the groundwork for a new generation of "Explainable ASP" (XASP) tools. By providing a formal proof theory that accounts for complex constraints and rejects circularity, the authors offer a robust foundation for building more transparent symbolic AI systems.

Future research is required to address the computational complexity of finding the shortest resolution proofs, which remains an intractable problem in the general case. Additionally, the authors suggest that integrating these algorithms into existing solvers like clingo and conducting user studies will be essential to determine how effectively these resolution-based proofs serve non-expert users in real-world debugging scenarios.

Summary updated

BibTeX
@inproceedings{wang2025witnesses,
  author = {Yisong Wang and Xianglong Wang and Zhongtao Xie and Thomas Eiter},
  title = {{Witnesses for Answer Sets of Basic Logic Programs}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/523},
}
Figure