rules in (9) and (10) are used to guarantee that ea h node has exa tly one outgoing edge, and the rules in (11) and (12) give the respe tive ondition on erning in oming edges.

We also need to he k that ea h node is rea hable from the rst node along the edges in the y le. For this, we introdu e module R
n = hR′, I′, O′, {e}i. The input signature of R
n is I
′ = O, and the output signature is O′ = {reached(x) | 1 ≤ x ≤
n}, where reached(x) tel ls that node x is rea
hable from the rst node. The set R′

ontains rules

$$\begin{array}{r l r l}{\mathrm{reached}(y)}&{{}\leftarrow}&{\mathsf{h c}(1,y)}\\ {\mathrm{reached}(y)}&{{}\leftarrow}&{\mathrm{reached}(x),\mathsf{h c}(x,y)}\\ {e}&{{}\leftarrow}&{\ \ \sim e,\sim\mathrm{reached}(y)}\end{array}$$

for ea h 2 ≤ x ≤ n and 1 ≤ y ≤ n. 

```
To generalize the stable model semanti
                               s to 
                                    over modules as well, we must
                                                             

```

expli ate the semanti al role of input atoms. To this end, we will follow an approa h4 from (Janhunen et al. 2007) and take input atoms into a ount in the denition of the redu t adopted from (Janhunen and Oikarinen 2007). It should be stressed that al l negative literals and literals involving input atoms get evaluated in the redu tion. Moreover, our denitions be ome equivalent with those proposed for normal programs (Gelfond and Lifs hitz 1988) and smodels programs

(Janhunen and Oikarinen 2007) if an empty input signature I = ∅ is additionally assumed. Using the same idea, a onventional smodels program, that is, a set of basi
 
onstraint rules R, 
an be viewed as a module hR, ∅, At(R), ∅i without any input atoms and all atoms visible.

Denition 4.3 Given a module P = h**R, I, O, H**i, the redu
t of R with respe
t to an interpretation M ⊆ At(P) and input signature I , denoted by RM,I, 
ontains 1. a rule a ← (B \ I) if and only if there is a 
hoi
e rule {A} ← B, ∼C in R su
h that a ∈ A ∩ M , B ∩ I ⊆ M , and M ∩ C = ∅; and 2. a rule a ← w
′ ≤ {B \ I = WB\I } if and only if there is a weight rule a ← w ≤
{B = WB, ∼C = WC } in R, and

$$w^{\prime}=\operatorname*{max}(0,w-\sum_{b\in B\cap I\cap M}w_{b}-\sum_{c\in C\setminus M}w_{c}).$$

As all o urren es of atoms in the input signature and all negative o urren es of atoms are evaluated, the generalized redu t RM,I is a positive program in the sense of (Janhunen and Oikarinen 2007) and thus it has a unique least model LM(RM,I ) ⊆
At(R) \ I .