bodies (Woltran 2008). The various notions of equivalence that can be formalized this way have recently been called *relativized hyperequivalence* (Truszczynski and Woltran 2008a; Truszczynski and Woltran 2008b).

Similarly as for uniform equivalence, semantic characterizations of relativized hyperequivalence have been obtained by means of a maximality criterion so far, and only for finite propositional settings. We address this issue and apply the same methods as for uniform equivalence in order to obtain alternative characterizations. They can be stated without any finiteness restrictions and easily lift to first-order settings over infinite domains.

The new contributions compared to (Fink 2008) can be summarized as follows:
- We provide full proofs for the characterizations of uniform equivalence, but also classical equivalence, answer-set equivalence, and strong equivalence, in terms of countermodels in HT, respectively in terms of *equivalence interpretations*, developed in (Fink 2008).

- We extend these ideas to relativized settings of equivalence and generalize the notion of relativized hyperequivalence to propositional theories. Abstracting from the notions of rule head and rule body, we obtain respective notions of relativization for theories. We provide novel semantical characterizations in terms of equivalence interpretations for this generalized setting, again without any finiteness restrictions.

- We lift these results to first-order theories by means of QHT, essentially introducing, besides uniform equivalence, relativized hyperequivalence for first-order theories under the most general form of answer-set semantics currently considered.

- We correct an informal claim that has been made in connection with a property which allows for a simplified treatment of extended signatures and holds for QHT
countermodels. Based on an erroneous example (Example 5 in (Fink 2008)), it was claimed that this property does not hold for QHT-models, which is not the case.

- Eventually, we reconsider logic programs and prove, using the established characterization, that uniform equivalence coincides for open and ordinary answer-set semantics, as well as other results which have been stated without proof in (Fink 2008).

Our results provide an elegant, uniform model-theoretic framework for the characterization of the different notions of equivalence considered in ASP. They generalize to firstorder theories without finiteness restrictions, and are relevant for practical ASP systems that handle finite non-ground programs over infinite domains.

In particular relativized notions of equivalence are relevant in practice. For instance, program composition from modular parts is an issue of increasing interest in ASP (Dao-Tran et al. 2009; Janhunen et al. 2009). It usually hinges on semantic properties specified for an interface
(input/output for 'calling' or connecting modules), i.e., properties that require compliance on a subset of the underlying language. Our results might be exploited to provide correctness guarantees for specific compositions.

Another benefit comes with the generalization to first-order theories. It facilitates and simplifies the study of combinations of ASP with other formalisms, or means for external data access, in a unifying formalism. Especially the combination of nonmonotonic rules with description logics is a highly relevant instance of such a combination. Our results can initiate or reduce difficulties in the study of modularity and optimization for such combined settings. (cf. (Fink and Pearce 2009) for preliminary work in this direction).