On Equivalence and Inconsistency of Answer Set Programs with External Sources

Christoph RedlAAAI 2017 · DOI

TL;DR

This paper extends the formal notions of equivalence and inconsistency from standard Answer Set Programming (ASP) to HEX-programs, which allow logic programs to interact with external data sources (like ontologies or web APIs). By providing a mathematical characterization of when two programs behave identically under any possible extension, the author lays the groundwork for more powerful optimization and debugging tools in modular knowledge representation.

What Problem Does This Paper Address?

In declarative programming, we often want to know if two programs are "equivalent." However, in ASP, simple equivalence (having the same answer sets) isn't enough because we often combine program modules. We need strong equivalence: two programs $P$ and $Q$ are strongly equivalent if $(P \cup R)$ and $(Q \cup R)$ have the same answer sets for any possible program $R$.

While this is well-understood for standard ASP, HEX-programs introduce two complications:

  1. External Sources: They use "external atoms" (e.g., &synonym[car](X)) that fetch data from outside the logic system.
  2. Different Semantics: HEX-programs typically use the FLP-reduct to handle non-monotonicity, whereas standard ASP uses the Gelfond-Lifschitz (GL) reduct.

The author addresses the gap in formalizing how these programs behave when extended by new rules or facts, and specifically how to identify "persistent inconsistency"—when a program remains inconsistent regardless of what external data or rules are added to it.

Methods

The paper's approach relies on two main pillars:

  • External Atom Inlining: The author utilizes a technique to "inline" external atoms, effectively rewriting a HEX-program into a standard ASP program (with auxiliary atoms). This allows the application of existing ASP theory to the more complex HEX setting.
  • Generalizing $\langle \mathcal{H}, \mathcal{B} \rangle$-Equivalence: The author lifts a framework originally proposed by Woltran (2007). This framework is highly flexible; by restricting the sets of atoms that can appear in the heads ($\mathcal{H}$) or bodies ($\mathcal{B}$) of the added program $R$, it can express strong equivalence, uniform equivalence, and everything in between.

The paper provides formal proofs that these characterizations hold even under the FLP-reduct semantics, which is a non-trivial result because the FLP-reduct does not always behave as "nicely" as the GL-reduct.

Datasets

Not discussed in the paper. As a theoretical research paper focused on formal semantics and proofs, it does not utilize empirical datasets or benchmarks.

Key Insights and Ideas

  • The Inlining Bridge: The most significant insight is that despite the "black box" nature of external sources, they can be formally modeled as internal choices within the program. This allows the author to prove that equivalence for HEX-programs can be checked using similar model-theoretic criteria as ordinary ASP.
  • Persistent Inconsistency: The paper introduces the concept of a program being "persistently inconsistent" relative to certain extensions. This is a vital "fail-fast" condition for solvers.
  • Unfounded Sets as a Tool: The author derives a criterion for checking persistent inconsistency based on unfounded sets. This is a practical breakthrough because many modern ASP solvers already use unfounded sets to prune search spaces, making this theoretical result directly implementable in existing software.
  • Broad Applicability: Because HEX-programs are a very general formalism, these results automatically apply to other ASP extensions, such as programs with aggregates or constraint ASP.

Key Results

  • Formal Characterization: The paper successfully defines $\langle \mathcal{H}, \mathcal{B} \rangle$-equivalence for HEX-programs and proves it is equivalent to comparing the $\langle \mathcal{H}, \mathcal{B} \rangle$-models of the programs.
  • Inconsistency Criterion: Proposition 7 provides a decision criterion for persistent inconsistency: a program is persistently inconsistent if every classical model of the program can be "defeated" by a smaller model of its reduct that doesn't change the atoms in the "head" set $\mathcal{H}$.
  • Algorithmic Outlook: The author demonstrates how these results can be used in program splitting. If a program is partitioned into components, and one component is found to be persistently inconsistent, the solver can stop early without evaluating subsequent components, potentially avoiding an exponential "grounding bottleneck."

Limitations and Future Work

  • Variable-Free Focus: The current results are primarily discussed for variable-free (ground) programs. While the author mentions that extensions to non-ground programs are possible, the formal details are left for future work.
  • Fine-Grained Distinctions: Currently, the framework does not distinguish between standard body atoms and input atoms passed to external sources. Refining this distinction could lead to even more precise equivalence criteria.
  • Implementation: While the paper provides the mathematical foundation, the actual integration of these checks into a high-performance HEX-solver (like DLVHEX) is an ongoing challenge mentioned in the outlook.

Summary updated

BibTeX
@inproceedings{redl2017equivalence,
  author = {Christoph Redl},
  title = {{On Equivalence and Inconsistency of Answer Set Programs with External Sources}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.1609/aaai.v31i1.10671},
}
Figure