Abstract
In modular logic programming, ensuring that a program component can be replaced by an optimized version without altering the global behavior is a fundamental challenge. This paper extends the theory of "hyperequivalence"—the guarantee of interchangeability across all possible contexts—from stable-model semantics to supported models and supported minimal models. By providing formal model-theoretic characterizations and mapping the computational complexity of these equivalences, the authors reveal unique properties of supported semantics, including a surprising collapse of strong and uniform equivalence and a complexity jump to the second level of the polynomial hierarchy for minimal models.
Introduction
In the field of nonmonotonic reasoning, adding new information to a system can lead to the retraction of previously held conclusions. This characteristic makes modular software development particularly difficult: simply ensuring that two programs, $P$ and $Q$, have the same models is insufficient to guarantee they will behave identically when embedded within a larger system. To address this, researchers use the concept of hyperequivalence. Two programs are considered hyperequivalent if, for any context program $R$, the combined programs $P \cup R$ and $Q \cup R$ are equivalent under a specific semantics.
While hyperequivalence has been studied extensively for stable-model semantics (the basis of Answer Set Programming), this paper explores its application to supported models. Based on Clark’s completion, supported models require that every atom in a model be "justified" by the head of a rule whose body is satisfied. This study further extends to supported minimal models, which are vital for knowledge representation tasks requiring parsimonious explanations.
Semantic Foundations and Methodology
The authors utilize a formal, model-theoretic approach to characterize equivalence, primarily relying on the $T_P$ operator (the one-step provability operator). This operator identifies what can be immediately derived from a program given a set of facts. The research demonstrates that for two programs to be equivalent under supported models, their $T_P$ operators must behave identically across their shared models.
To capture the essence of a program's behavior, the authors introduce new semantic structures—sets of pairs of interpretations—analogous to the "SE-models" used to characterize strong equivalence in stable semantics. They also employ relativization, analyzing how equivalence is affected when the "alphabet" (the set of allowed atoms) available to the context program $R$ is restricted in either its rule heads or bodies.
Key Theoretical Insights
The Collapse of Strong and Uniform Equivalence
One of the most significant findings is that for supported models, the distinction between "strong equivalence" (where the context $R$ can be any program) and "uniform equivalence" (where $R$ is restricted to a set of facts) disappears. This is a major departure from stable-model semantics, where these two notions are distinct. In the realm of supported models, these two forms of hyperequivalence collapse into a single property.
The Role of Rule Bodies and Shifting
The research highlights that in supported-model semantics, the specific atoms allowed in the bodies of rules within the context program $R$ do not affect equivalence. However, for minimal supported models, the body alphabet becomes a critical factor. Additionally, the authors demonstrate a "shifting property," showing that disjunctive programs (rules with multiple possible outcomes in the head) can be transformed into normal programs without losing their supported model properties, simplifying the broader theoretical framework.
Complexity and Results
The paper identifies a specific "complexity cliff" regarding the verification of these equivalences:
- Supp-Equivalence: Deciding if two programs are equivalent under supported models relative to any class of programs is coNP-complete.
- Suppmin-Equivalence:
- When the context is unrestricted, the problem remains coNP-complete.
- When the context is restricted to a specific finite set of atoms (relativized equivalence), the complexity jumps to $\Pi^P_2$-complete.
These results are supported by characterization theorems (Theorems 3, 10, and 14) that allow researchers to verify equivalence by examining programs $P$ and $Q$ directly, bypassing the need to test every potential context $R$.
Conclusion and Future Directions
This work provides a comprehensive map of hyperequivalence for supported model semantics, filling a significant gap in the theory of logic programming. While the current study focuses on propositional logic, future research may extend these findings to first-order programs with variables. Other promising avenues include generalizing these techniques through the language of partial operators on boolean algebras and applying hyperequivalence to Moore’s autoepistemic logic, particularly regarding moderately grounded expansions.
Summary updated