The other notion of program equivalence introduced in [2], *strong update equivalence on common rules*, or SUC-equivalence, is incomparable in terms of strength to our new notions of equivalence. On the one hand, SR- and SMR-equivalent programs such as { ∼p. } and { ∼p., ← p. } are not SUC-equivalent. On the other hand, programs such as { **p., q** ← p. } and { **q., p** ← q. } are neither SR- nor SMR-equivalent, but they are SUC-equivalent. We believe that both of these examples are more appropriately treated by the new notions of equivalence.

The introduction of canonical rules, which form a set of representatives of rule equivalence classes induced by SE-models, also reveals the exact expressivity of SE-model semantics with respect to a single rule. From their definition we can see that SE-models are capable of distinguishing between any pair of rules, except for (1) a pair of rules that only differ in the number of repetitions of literals in their heads and bodies; (2) an integrity constraint and a rule whose head only contains negative literals. We believe that in the former case, there is little reason to distinguish between such rules and so the transition from rules to their SE-models has the positive effect of stripping away of unnecessary details. However, the latter case has more serious consequences. Although rules such as

## ∼P ← Q. And ← **P, Q.**

are usually considered to carry the same meaning, some existing work suggests that they should be treated differently - while the former rule gives a reason for atom p to become false whenever q is true, the latter rule simply states that the two atoms cannot be true at the same time, without specifying a way to resolve this situation if it were to arise [4, 8]. If we view a rule through the set of its SE-models, we cannot distinguish these two kinds of rules anymore. Whenever this is important, either *strong update equivalence* is used, which is perhaps too sensitive to the syntax of rules, or a new characterisation of Answer-Set Programming needs to be discovered, namely one that is not based on the logic of Here-and-There [16, 17].

## Acknowledgement

We would like to thank Han The Anh, Matthias Knorr and the anonymous reviewers for their comments that helped to improve the paper. Martin Slota is supported by FCT scholarship SFRH / BD / 38214 / 2007.

## References
