A Constructive semantic characterization of aggregates in answer set programming

TLDR

The study references prior work from 2004. The note introduces a monotone, continuous fixpoint operator for computing answer sets of programs with aggregates. The operator is based on aggregate solutions and links answer set checking complexity to the cost of verifying aggregate solutions. The operator matches the three‑valued immediate consequence operator under certain conditions and its semantics are related to other aggregate‑logic programming proposals.

Abstract

Abstract This technical note describes a monotone and continuous fixpoint operator to compute the answer sets of programs with aggregates. The fixpoint operator relies on the notion of aggregate solution . Under certain conditions, this operator behaves identically to the three-valued immediate consequence operator Φ aggr P for aggregate programs, independently proposed in Pelov (2004) and Pelov et al. (2004). This operator allows us to closely tie the computational complexity of the answer set checking and answer sets existence problems to the cost of checking a solution of the aggregates in the program. Finally, we relate the semantics described by the operator to other proposals for logic programming with aggregates.