On the Properties of GZ-Aggregates in Answer Set Programming

Mario Alviano, Nicola LeoneIJCAI 2016

Introduction

Answer Set Programming (ASP) has emerged as a robust paradigm for solving complex combinatorial problems. A critical component of its expressive power is the use of aggregates—functions like counts, sums, or averages that operate over sets of atoms. However, the integration of aggregates into recursive definitions poses significant semantic challenges. Traditional approaches, such as F-stable semantics, can occasionally permit "vicious circles," where an atom's truth is justified by a self-referential loop through an aggregate.

To address this, Gelfond and Zhang proposed the GZ-semantics, which strictly adheres to the Vicious Circle Principle. This principle mandates that the truth of an atom must be established without any reliance, even indirect, on the atom itself. This paper provides a comprehensive theoretical and practical analysis of GZ-aggregates, exploring their computational complexity and providing methods for their implementation in existing ASP solvers.

Computational Complexity Analysis

The authors categorize aggregates into three distinct classes based on their mathematical properties:

  1. Monotone (M): Where adding elements to the set can only satisfy the aggregate condition.
  2. Convex (C): Where the condition holds within a specific range of values.
  3. Non-convex (N): All other aggregate types.

The study maps the computational cost of two fundamental reasoning tasks: coherence testing (determining if a stable model exists) and cautious reasoning (identifying atoms true in all stable models).

A surprising finding of this analysis is the "Complexity Paradox." While stricter semantics often increase computational difficulty, GZ-semantics actually decreases the complexity for non-convex aggregates in certain fragments. For instance, in programs without disjunction, GZ-semantics brings the complexity of non-convex aggregates down to NP-complete, whereas standard semantics would typically require a more difficult $\Sigma^P_2$ check. Conversely, for monotone aggregates, GZ-semantics can increase complexity, enabling them to simulate features like integrity constraints and default negation.

Compilation and Implementation

To bridge the gap between theory and practice, the paper introduces two "rewriting" techniques that translate GZ-programs into standard ASP formats compatible with high-performance solvers like Clingo or DLV.

  • First Rewriting: Focuses on compactness, introducing minimal auxiliary variables. However, it can lead to higher computational overhead during solver execution.
  • Second Rewriting: Introduces more auxiliary variables but ensures that the resulting aggregates are "stratified" (non-recursive). This structure is significantly easier for modern solvers to optimize and process efficiently.

The authors proved these translations to be "faithful" and "modular," ensuring that the stable models of the rewritten programs correspond exactly to those of the original GZ-programs.

Key Results

The theoretical findings are summarized in the complexity table below. These results highlight the shifts in complexity classes when moving to GZ-semantics across different program fragments, such as those involving negation (~) or disjunction (V).

Complexity of Coherence Testing and Cautious Reasoning under GZ-semantics.

Key highlights from the analysis include:

  • Coherence Testing: For monotone aggregates, complexity can jump to NP-complete or $\Sigma^P_2$-complete under GZ-semantics.
  • Non-Convex Efficiency: In programs without disjunction, GZ-semantics reduces the complexity of non-convex aggregates to NP-complete.
  • Practicality: The prototype implementation demonstrates that the Vicious Circle Principle can be enforced effectively using existing solver technology without the need for specialized engines.

Conclusion and Future Work

This work establishes a rigorous foundation for GZ-aggregates in ASP. While the second rewriting technique is robust, the introduction of numerous auxiliary atoms remains a potential bottleneck for extremely large-scale instances. Future research will focus on optimizing these translations to minimize auxiliary overhead and investigating the application of GZ-properties to other logic programming extensions, such as those handling qualitative preferences or uncertainty.

This summary is based on the paper "On the Properties of GZ-Aggregates in Answer Set Programming" presented at IJCAI-16.

Summary updated

BibTeX
@inproceedings{alviano2016properties,
  author = {Mario Alviano and Nicola Leone},
  title = {{On the Properties of GZ-Aggregates in Answer Set Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure