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).
For the sake of completeness, we will review the translation of @cite_5 , presented using the notation of our paper. Given a ground logic program with aggregates @math , @math denotes the ground normal logic program obtained after the translation. The process begins with the translation of each aggregate atom @math of the form @math into a disjunction @math , where @math , and each @math is a conjunction of the form [ l s_1 l l H ( ) s_2 l ] The construction of @math considers only the pairs @math that satisfy the following condition: each interpretation @math such that @math and @math must satisfy @math . The translation @math is then created by replacing rules with disjunction in the body by a set of standard rules in a straightforward way. For example, the rule [ a (b c), d ] is replaced by the two rules [ ] From the definitions of @math and of aggregate solutions, we have the following simple lemma: We next show that fixed point answer sets of @math are answer sets of @math .
@cite_5
80590317
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.