The paper presents two equivalent definitions of answer sets for logic programs with aggregates. These definitions build on the notion of unfolding of aggregates, and they are aimed at creating methodologies to translate logic programs with aggregates to normal logic programs or positive programs, whose answer set semantics can be used to defined the semantics of the original programs. The first definition provides an alternative view of the semantics for logic programming with aggregates described by The second definition is similar to the traditional answer set definition for normal logic programs, in that, given a logic program with aggregates and an interpretation, the unfolding process produces a positive program. The paper shows how this definition can be extended to consider aggregates in the head of the rules. The proposed views of logic programming with aggregates are simple and coincide with the ultimate stable model semantics, and with other semantic characterizations for large classes of program (e.g., programs with monotone aggregates and programs that are aggregate-stratified). Moreover, it can be directly employed to support an implementation using available answer set solvers. The paper describes a system, called ASP^A, that is capable of computing answer sets of programs with arbitrary (e.g., recursively defined) aggregates.
In this subsection, we investigate the relationship between -answer sets and the notion of answer set defined by in @cite_41 . The notion of answer set proposed in @cite_41 is based on a new notion of reduct, defined as follows. Given a program @math and a set of atoms @math , the reduct of P with respect to S , denoted by @math , is obtained by removing from @math those rules whose body is not satisfied by @math . In other words, [ ^S P = r r ground(P), S body(r) . ] The novelty of this reduct is that it remove aggregate atoms and negation-as-failure literals satisfied by @math .
@cite_41
50549667
In recent years, Answer Set Programming ASP, logic programming under the stable model or answer set semantics, has seen several extensions by generalizing the notion of an atom in these programs: be it aggregate atoms, HEX atoms, generalized quantifiers, or abstract constraints, the idea is to have more complicated satisfaction patterns in the lattice of Herbrand interpretations than traditional, simple atoms. In this paper we refer to any of these constructs as generalized atoms. It is known that programs with generalized atoms that have monotonic or antimonotonic satisfaction patterns do not increase complexity with respect to programs with simple atoms if satisfaction of the generalized atoms can be decided in polynomial time under most semantics. It is also known that generalized atoms that are nonmonotonic being neither monotonic nor antimonotonic can, but need not, increase the complexity by one level in the polynomial hierarchy if non-disjunctive programs under the FLP semantics are considered. In this paper we provide the precise boundary of this complexity gap: programs with convex generalized atom never increase complexity, while allowing a single non-convex generalized atom under reasonable conditions always does. We also discuss several implications of this result in practice.