under the semantics of [Niemel¨a and Simons, 2000], 0 ≤ {p = 2, p = −1} is different from 0 ≤ {p = 1}. In fact,

$$p\leftarrow0\leq\{p=1\}$$
p ← 0 ≤ {p = 1} (28)
has stable model ∅, the same of (27), while (26) has none. Notice that summing weights that are all positive or all negative preserves stable models under both semantics.

The preliminary step of removing negative weights can be seen as a way of making weight constraints either monotone or antimonotone. This keeps the problem of the existence of a stable model in class NP, while we have seen in Section 3.5 that, under our semantics, even simple aggregates with the same intuitive meaning of 0 ≤ {p = 1, q = −1} bring the same problem to class Σ
P 2
.

## 3.6.2 Pdb-Aggregates

A *PDB-aggregate* is an expression of the form (6), where F1, . . . , Fn are literals.

A *program with PDB-aggregates* is a set of rules of the form a ← A1 **∧ · · · ∧** Am, where m ≥ 0, a is an atom and A1, . . . , Am are PDB-aggregates.

As in the case of programs with weight constraints, a program with PDBaggregates is a generalization of a traditional program, by identifying each literal l in the bodies of traditional programs by aggregate sumh{l = 1**}i ≥** 1.

The semantics of [Pelov *et al.*, 2003] for programs with PDB-aggregates is based on a procedure that transforms programs with such aggregates into traditional programs.13 The procedure can be seen consisting of two parts. The first one essentially consists in rewriting each aggregate as a nested expression.14 The second part "unfolds" each rule into a strongly equivalent set of traditional rules.

For our comparisons, only the first part is needed: each PDB-aggregate A of the form oph{l1 = w1, . . . , ln = wn**}i ≺** N
is replaced by the following nested expression Atr I1,I2:I1⊆I2⊆{1,...,n} and for all I such that I1 ⊆ I ⊆ I2, op(WI ) ≺ N

$$G_{(I_{1},I_{2})}$$
