Elementary Sets of Logic Programs

Martin Gebser, Joohyung Lee, Yuliya LierlerAAAI 2006

Abstract

This paper introduces the concept of "elementary sets" as a streamlined alternative to traditional loops in Answer Set Programming (ASP). By redefining the relationship between logic program completion and stable models through the lens of outbound rules, the authors provide a more concise characterization of stability. This framework simplifies previous graph-theoretic definitions and, for the first time, successfully extends the theory of elementary loops to disjunctive logic programs. The results offer a path toward more efficient SAT-based ASP solvers by reducing the redundancy of loop formulas.

Introduction

In the field of Answer Set Programming (ASP), the search for stable models (or answer sets) is a central challenge. A landmark development in this area was the discovery by Lin and Zhao (2004) that stable models are precisely the models of a program's completion that also satisfy a specific set of "loop formulas." While this provided a clear logical path to finding answer sets, it introduced a significant computational hurdle: a logic program can contain an exponential number of loops, making the generation and verification of all loop formulas prohibitively expensive.

Subsequent research aimed to identify "elementary loops"—a subset of loops sufficient to characterize stability—to mitigate this overhead. However, early definitions were mathematically cumbersome, heavily dependent on complex graph structures, and failed to generalize correctly to disjunctive logic programs (programs where a rule head may contain multiple atoms). This paper addresses these limitations by introducing elementary sets, a purely logical refinement of the loop concept.

Methodology: From Graphs to Outbound Rules

The authors shift the focus away from complex dependency graphs toward a logic-based definition centered on "outbound" rules. This approach provides a unified framework for both standard and disjunctive programs.

The Outbound Definition

At the heart of this new characterization is the concept of support. A subset of atoms is considered "outbound" if there exists a rule in the program that can support an atom within that subset using only atoms from outside the larger set.

Defining Elementary Sets

Using this foundation, an elementary set is defined as a set where all of its nonempty proper subsets are outbound within it. Unlike previous iterations, this definition does not rely on a specific graph representation, though the authors demonstrate that for standard (nondisjunctive) programs, these sets can still be identified using a simplified "elementary subgraph" of the standard positive dependency graph.

Extension to Disjunctive Logic

One of the paper's primary contributions is the generalization of this logic to disjunctive programs. By redefining outbound rules to accommodate multiple atoms in a rule head, the authors bridge a long-standing gap in ASP theory, providing a consistent definition that behaves logically across all program types.

Key Insights and Theoretical Results

The introduction of elementary sets yields several significant theoretical insights:

  1. Connection to Unfounded Sets: The authors prove that "elementarily unfounded sets" are exactly the minimal nonempty unfounded sets. This creates a direct link between elementary sets and the well-established theory of unfounded sets used in modern ASP solvers, providing a formal justification for the efficiency of the new definition.
  2. Redundancy Reduction: The paper demonstrates that a vast number of loops are redundant. By focusing exclusively on elementary sets, one can ignore these redundant loops without losing the ability to identify stable models. This is formalized in Theorem 1(d), which states that a model is stable if and only if it satisfies the loop formulas for all elementary sets.
  3. Computational Complexity: The authors provide a clear picture of the computational landscape. For standard programs, deciding if a set is elementary is tractable (polynomial time). However, for disjunctive programs, the problem becomes coNP-complete. This result is significant as it mirrors the inherent complexity of "unfounded-freeness" in disjunctive ASP, explaining why these programs are fundamentally harder to solve.

Discussion and Future Work

The primary limitation of this approach lies in the computational complexity of the disjunctive case. Because identifying elementary sets is coNP-complete for disjunctive programs, implementing a general-purpose solver that utilizes these sets for all disjunctive problems remains a challenge.

However, the authors identify a promising middle ground in head-cycle-free programs. For this specific class of disjunctive programs, the identification of elementary sets remains tractable. The paper concludes by suggesting that the integration of elementary set calculations into SAT-based solvers like CMODELS could yield substantial performance gains in practice. By focusing on the most essential logical structures, elementary sets provide a robust foundation for the next generation of ASP technology.

Summary updated

BibTeX
@inproceedings{gebser2006elementary,
  author = {Martin Gebser and Joohyung Lee and Yuliya Lierler},
  title = {{Elementary Sets of Logic Programs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure