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 @math for aggregate programs, independently proposed 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. To appear in Theory and Practice of Logic Programming (TPLP).
The work of @cite_5 @cite_2 @cite_11 contains an elegant generalization of several semantics of logic programs to logic programs with aggregates. The key idea in this work is the use of approximation theory in defining several semantics for logic programs with aggregates (e.g., two-valued semantics, ultimate three-valued stable semantics, three-valued stable model semantics). In particular, in @cite_11 , the authors describe a fixpoint operator, called @math , operating on 3-valued interpretations and parameterized by the choice of approximating aggregates.
@cite_5 @cite_11 @cite_2
80590317 1520574003 125332145
Dept. of Computer Science, K.U.LeuvenCelestijnenlaan 200A, B-3001 Heverlee, BelgiumE-mail: pelov,marcd,maurice @cs.kuleuven.ac.beAbstract. We deﬁne a translation of aggregate programs to normal lo-gic programs which preserves the set of partial stable models. We thendeﬁne the classes of deﬁnite and stratiﬁed aggregate programs and showthat the translation of such programs are, respectively, deﬁnite and strat-iﬁed logic programs. Consequently these two classes of programs havea single partial stable model which is two-valued and is also the well-founded model. Our deﬁnition of stratiﬁcation is more general than theexisting one and covers a strictly larger class of programs. We introduce a family of partial stable model semantics for logic programs with arbitrary aggregate relations. The semantics are parametrized by the interpretation of aggregate relations in three-valued logic. Any semantics in this family satisfies two important properties: (i) it extends the partial stable semantics for normal logic programs and (ii) total stable models are always minimal. We also give a specific instance of the semantics and show that it has several attractive features.