Definition 4 A disjunctive program Π is called *e-tight* **if every elementary loop of Π is trivial.**
Since every elementary loop is a loop, it is clear that a tight program is e-tight as well. But is the class of e-tight programs more general than the class of tight programs? One reason why this is an interesting question to consider is because, if so, it would lead to a generalization of Fages' theorem (Fages 1994), which would yield a more general class of programs for which the stable model semantics coincides with the completion semantics. However, it turns out that e-tight programs are not more general than tight programs.

Proposition 12 For any disjunctive program Π, Π is e-tight iff Π is tight.

Proof. *From left to right:* **Assume that Π is not tight. Then there is a minimal**
nontrivial loop X **of Π, and the subgraph of the dependency graph of Π induced** by X **yields a simple directed cycle. That is, for any nonempty proper subset** Y of X, there is a rule (12) in Π such that A∩X = {a}, B ∩X = {b} **for atoms** a ∈ Y , b ∈ X \ Y . This shows that Y is outbound in X for Π, so that X **is a nontrivial**
elementary loop of Π.

From right to left is clear.

This result also tells us that the notion of an inherently tight program **does not**
become more general by referring to elementary loops, i.e., by replacing the part
"Π′is tight" in the statement of Definition 3 with "Π′**is e-tight."**

## 6 Hef Programs And Stability Checking

For a disjunctive program, the problem of deciding whether a given model is stable is coNP**-complete (Eiter and Gottlob 1995). On the other hand, in view of Theorem 5, the same problem is tractable for HEF programs. In order to check the**
stability of a model in polynomial time, Leone *et al.* **(1997) presented an operational framework, which, for HCF programs, allows for deciding whether a model**
is stable. Given a disjunctive program Π and sets X, Y **of atoms, they defined a**
sequence R0Π,X(Y ), R1Π,X(Y ), . . . , which converges to a limit RωΠ,X(Y **), in the following way:**
- R0Π,X(Y ) = Y and
- R
i+1 Π,X(Y ) is obtained by removing every atom a from RiΠ,X(Y **) such that some**
rule (12) in ΠX satisfies A ∩ (X ∪ {a}) = {a} and B ∩ RiΠ,X(Y ) = ∅.

12 The disjunctive rules considered in (Leone et al. 1997) do not admit double negations in rule bodies, but its (dis)use merely affects conditions like X |= B, F (or X 6|= B, F) determining ΠX**, while it is inconsequential otherwise. Hence, the following results remain valid for disjunctive programs whose rules are of the form (12).**
12 If Y is a subset of X**, the condition "**A ∩ (X ∪ {a}) = {a}**" can be replaced with "**A ∩ X = {a}"
without altering RωΠ,X(Y ).