Definition 12 A QHT-interpretation M = h**I, J, K**i is a *QHT-hyperequivalence interpretation wrt.* L
+
and L
− of a first-order theory Γ iff h**I, K, K**i is L
+-total and there exists a QHT-interpretation hI, J′, Ki such that J = J
′
|L+∪L− and hI, J′, Ki is L
+-closed in Es(Γ).

The set of QHT-hyperequivalence interpretations wrt. L
+ and L
− of a first-order theory Γ
is denoted by EL
+
L− (Γ).

Eventually, we arrive at a characterization of relativized hyperequivalence for general first-order theories under answer-set semantics, where contexts are restricted on the predicate level.

## Theorem 8

Two first-order theories Γ1, Γ2 are relativized hyperequivalent wrt. L
+ and L
− if and only if they coincide on their QHT-hyperequivalence interpretations wrt. L
+ and L
−, symbolically Γ1 L
+
L−≡ Γ2 iff EL
+
L− (Γ1) = EL
+
L− (Γ2).

In the same way as for propositional theories, the prominent notions of equivalence are obtained as special cases, and the framework gives rise to relativized notions of strong and uniform equivalence for general first-order theories under answer-set semantics. Also in analogy, the role of factual theories is governed by Proposition 8, yielding the following:
Corollary 6 Two first-order theories Γ1, Γ2 are *relativized hyperequivalent wrt. extended* L
+-L
−*-theories* if and only if they coincide on their QHT-hyperequivalence interpretations wrt. L
+
and L
−.

## 5 Non-Ground Logic Programs

In this section we apply the characterizations obtained for first-order theories to non-ground logic programs under various extended semantics—compared to the traditional semantics in terms of Herbrand interpretations. For a proper treatment of these issues, further background is required and introduced (succinctly, but at sufficient detail) below.

In non-ground logic programming, we restrict to a function-free first-order signature L = hF,Pi (i.e., F contains object constants only) without equality. A *program* Π (over L) is a set of rules (over L) of the form (1). A rule r is *safe* if each variable occurring in H(r) ∪ B−(r) also occurs in B+(r); a rule r is *ground*, if all atoms occurring in it are ground. A program is safe, respectively ground, if all of its rules enjoy this property.

Given Π over L and a universe U, let L
U be the extension of L as before. The *grounding* of Π wrt. U and an interpretation I|LF of LF on U is defined as the set grd U

(Π, I|LF )
of ground rules obtained from r ∈ Π by (i) replacing any constant c in r by cε such that I|LF (c) = ε, and (ii) all possible substitutions of elements in CU for the variables in r.

Adapted from (Gelfond and Lifschitz 1991), the *reduct* of a program Π with respect to a first-order interpretation I = hI|LF , I|CU
i on universe U, in symbols grd U (Π, I|LF )
I, is given by the set of rules a1 ∨ · · · ∨ ak ← b1**, . . . , b**m, obtained from rules in grd U (Π, I|LF ) of the form (1), such that I |= ai for all **k < i** ≤ l and I 6|= bj for all **m < j** ≤ n.