181
Stable and Perfect Model Semantics
This contradiction shows that I [P ] must be a perfect model for P , as required.
•
6.3.8 Program Since locally stratified programs are a generalization of locally hierarchical programs, it is clear that each locally hierarchical program
has a unique perfect model. This does not hold, however, for Φ
∗ -accessible
programs. Indeed, the program
p ← ¬q
q ← r, ¬p
is Φ
∗ -accessible (even acceptable) with respect to the unique supported model
M = {p}. However, I = {q} is also a model for this program, and while I
is preferable to M , M , in turn, is also preferable to I, so P does not have a
perfect model.
We finally return to the special case of stratified programs. We temporarily
introduce the powers of an operator T mapping a complete lattice to itself:
8
T ↑ 0(I) = I
T ↑ (n + 1)(I) = T (T ↑ n(I)) ∪ T ↑ n(I)
∞
T ↑ ω(I) =
T ↑ n(I).
n=0
Of course, T ↑ n(I) is not equal to T
n (I) unless T happens to be monotonic
and I ⊆ T (I). Indeed, the sequence (T ↑ n(I)) n is always monotonic increasing
whether or not T is monotonic. However, this concept can be used to construct
an associated model M P for any stratified program P as follows. We put M 0 =
∅, M 1 = T P1 ↑ ω(M 0 ), . . . , M m = T Pm ↑ ω(M m−1 ). Finally, let M P = M m .
We will show that M P is the perfect model for P , for stratified P . To do
this, it will be convenient to introduce the concept T ⇑ n(I) for a mapping
T : I P → I P and I ∈ I P . In fact, T ⇑ n(I) is defined inductively as follows:
T ⇑ 0(I) = I
T ⇑ (n + 1)(I) = T (T ⇑ n(I)) ∪ I
∞
T ⇑ ω(I) =
T ⇑ n(I).
n=0
6.3.9 Theorem Let P be a stratified normal logic program. Then I [P ] = M P .
Proof: As usual, we take the stratification to be P = P 1 ∪ . . . ∪ P m , and we
will show by induction that I k = M k for k = 1, . . . , m and that I k = M m for
k > m. From this we clearly have I [P ] = M m = M P , as required.
8 This and the following construction of M P was introduced in [Apt et al., 1988].
Stable and Perfect Model Semantics
This contradiction shows that I [P ] must be a perfect model for P , as required.
•
6.3.8 Program Since locally stratified programs are a generalization of locally hierarchical programs, it is clear that each locally hierarchical program
has a unique perfect model. This does not hold, however, for Φ
∗ -accessible
programs. Indeed, the program
p ← ¬q
q ← r, ¬p
is Φ
∗ -accessible (even acceptable) with respect to the unique supported model
M = {p}. However, I = {q} is also a model for this program, and while I
is preferable to M , M , in turn, is also preferable to I, so P does not have a
perfect model.
We finally return to the special case of stratified programs. We temporarily
introduce the powers of an operator T mapping a complete lattice to itself:
8
T ↑ 0(I) = I
T ↑ (n + 1)(I) = T (T ↑ n(I)) ∪ T ↑ n(I)
∞
T ↑ ω(I) =
T ↑ n(I).
n=0
Of course, T ↑ n(I) is not equal to T
n (I) unless T happens to be monotonic
and I ⊆ T (I). Indeed, the sequence (T ↑ n(I)) n is always monotonic increasing
whether or not T is monotonic. However, this concept can be used to construct
an associated model M P for any stratified program P as follows. We put M 0 =
∅, M 1 = T P1 ↑ ω(M 0 ), . . . , M m = T Pm ↑ ω(M m−1 ). Finally, let M P = M m .
We will show that M P is the perfect model for P , for stratified P . To do
this, it will be convenient to introduce the concept T ⇑ n(I) for a mapping
T : I P → I P and I ∈ I P . In fact, T ⇑ n(I) is defined inductively as follows:
T ⇑ 0(I) = I
T ⇑ (n + 1)(I) = T (T ⇑ n(I)) ∪ I
∞
T ⇑ ω(I) =
T ⇑ n(I).
n=0
6.3.9 Theorem Let P be a stratified normal logic program. Then I [P ] = M P .
Proof: As usual, we take the stratification to be P = P 1 ∪ . . . ∪ P m , and we
will show by induction that I k = M k for k = 1, . . . , m and that I k = M m for
k > m. From this we clearly have I [P ] = M m = M P , as required.
8 This and the following construction of M P was introduced in [Apt et al., 1988].