p q qr ✮
Fig. 2. The elementary subgraph of {p, q, r} **for Program Π**1 For any set X **of atoms that occur in a nondisjunctive program Π, we define:**
EC0Π(X) = ∅ ,
EC i+1 Π (X) = {(a1, b) | **there is a rule (3) in Π such that** a1 ∈ X,
b ∈ B ∩ X, and all atoms in B ∩ X **belong to the**
same strongly connected component in (X,ECiΠ(X))} ,
EC Π(X) = Si≥0EC iΠ(X) .

This is a "bottom-up" construction based on strongly connected components, i.e.,
maximal strongly connected subgraphs of a given graph. Thus ECiΠ(X**) is a subset**
of ECi+1 Π (X), and the graph (X,EC Π(X**)) is a subgraph of the positive dependency**
graph of Π. We call the graph (X,EC Π(X)) the *elementary subgraph* of X **for Π.**
Figure 2 shows the elementary subgraph of {p, q, r} for Π1**, which is not strongly**
connected.

The following theorem is similar to Theorem 10 from (Gebser and Schaub 2005),
but instead of referring to the notion of a body-head dependency **graph, it refers** to the notion of an elementary subgraph.

Theorem 3 For any nondisjunctive program Π and any nonempty set X **of atoms that occur**
in Π, X is an elementary loop of Π iff the elementary subgraph of X **for Π is strongly**
connected.

Since an elementary subgraph can be constructed in polynomial time, the problem of deciding whether a given set of atoms is an elementary loop of a nondisjunctive program is tractable.

## 2.5 Comparison With Gebser-Schaub Definition

In this section, we compare our reformulation of elementary loops with the original definition by Gebser and Schaub (2005) for nondisjunctive programs.

Let Π be a nondisjunctive program. A loop of Π is called *trivial* **if it consists of**
a single atom such that the dependency graph of Π does not contain **an edge from**
the atom to itself, and *nontrivial* otherwise.8 For a nontrivial loop L **of Π, let**
- R
−
Π(L) = {(3) ∈ Π | a1 ∈ L, B ∩ L = ∅}**, and**
- R
+
Π(L) = {(3) ∈ Π | a1 ∈ **L, B** ∩ L 6= ∅}.

Definition 1 (**(Gebser and Schaub 2005)**) A nontrivial loop L of a nondisjunctive program Π is called a *GS-elementary loop* of Π if R
−
Π
(L
′) ∩ R
+
Π
(L) 6= ∅ **for all proper subsets** L
′ of L **that are nontrivial loops**
of Π.

8 In (Lin and Zhao 2004) and (Gebser and Schaub 2005), loops were defined to be nontrivial.