Eliminating Disjunction from Propositional Logic Programs under Stable Model Preservation

Thomas Eiter, Michael Fink, Hans Tompits, Stefan WoltranAnswer Set Programming 2003 · OpenReview

Introduction

In the field of Answer Set Programming (ASP), disjunctive logic programs (DLPs) provide a powerful formalism for knowledge representation, allowing rules to contain multiple atoms in their heads (e.g., $A \vee B \leftarrow C$). This disjunction increases the expressive power of the language, enabling the solution of problems at the second level of the polynomial hierarchy. However, this power comes at a cost: increased computational complexity and greater difficulty in program optimization.

This paper investigates the conditions under which disjunction can be treated as "syntactic sugar" and eliminated in favor of normal logic programs (NLPs) without altering the program's semantics. The authors analyze this problem across three distinct levels of equivalence: ordinary, uniform, and strong equivalence.

Theoretical Framework: The Logic of Here-and-There

To analyze the equivalence of logic programs, the authors rely on the Logic of Here-and-There (HT), a non-classical logic that serves as the semantic foundation for stable models. Central to this approach are SE-models (Strong Equivalence models), represented as pairs of interpretations $(X, Y)$. In this framework, $X$ represents what is true "here" (a possible world), while $Y$ represents what is true "there" (the final stable model), with the constraint that $X \subseteq Y$.

Here-Intersection

A primary contribution of this work is the introduction of a novel semantic operation called here-intersection. If $(X, Y)$ and $(X', Y)$ are both SE-models of a program, their here-intersection is defined as $(X \cap X', Y)$. This operation is critical for identifying when a disjunctive program can be simplified under the strictest forms of equivalence.

Conditions for Disjunction Elimination

The authors demonstrate that the possibility of eliminating disjunction depends entirely on the required level of equivalence preservation:

  1. Ordinary Equivalence: Two programs are ordinarily equivalent if they share the same set of stable models. The authors prove that for any DLP, there exists an ordinarily equivalent NLP.
  2. Uniform Equivalence: Programs remain equivalent even when supplemented with arbitrary sets of input facts. The authors show that disjunction is also always theoretically eliminable under uniform equivalence.
  3. Strong Equivalence: This is the strictest criterion, requiring programs to remain equivalent when composed with any arbitrary set of additional rules. The authors find that strong equivalence is the only case where elimination is not always possible.

The Semantic Criterion for Strong Equivalence

The paper establishes that a DLP $P$ can be transformed into a strongly equivalent NLP if and only if the SE-models of $P$ are closed under here-intersection. This property is analogous to the requirement that Horn formulas in classical logic be closed under intersection. If a program fails this semantic test, the disjunction is essential to its behavior under composition.

Complexity and Transformations

Beyond existence proofs, the authors provide constructive "recipes" for transformation. They demonstrate how to rewrite disjunctive rules into sets of normal rules by considering the minimal SE-models of the program. However, they identify two significant hurdles for practical implementation:

  • Computational Complexity: Determining whether a program meets the criterion for normalization under strong equivalence is coNP-complete.
  • Exponential Blowup: The authors prove that any translation from DLPs to NLPs will, in the worst case, result in an exponential increase in program size (unless the Polynomial Hierarchy collapses). This explains why disjunction remains a vital tool in ASP despite the theoretical possibility of its removal.

Conclusion and Future Work

This research clarifies the relationship between disjunctive and normal logic programs, showing that the "extra power" of disjunction is primarily manifest in how programs behave when integrated with other rules. While the exponential size of normalized programs limits the immediate practical application of these transformations, the criteria developed provide a foundation for building more sophisticated ASP simplifiers and optimizers.

Future research directions include extending these propositional results to Datalog programs with variables, exploring the use of auxiliary variables to mitigate the exponential blowup in program size, and investigating the practical trade-offs between program size and solver performance in real-world ASP applications.

Summary updated

BibTeX
@inproceedings{eiter2003eliminating,
  author = {Thomas Eiter and Michael Fink and Hans Tompits and Stefan Woltran},
  title = {{Eliminating Disjunction from Propositional Logic Programs under Stable Model Preservation}},
  booktitle = {Answer Set Programming},
  year = {2003},
  url = {https://openreview.net/forum?id=YviWPNEqF8},
}
Figure