112
Mathematical Aspects of Logic Programming Semantics
4.6.17 Example Consider again the program P of Example 3.3.6
p(a) ←
p(s(X)) ← ¬p(X)
and note that P is not stratified nor even locally stratified. Define the level
mapping l on B P by l(p(s
n (a))) = n for each n. We note that in this
case T P is not non-expansive, for if we take I 1 = {p(a), p(s(a))} and I 2 =
{p(a), p(s(a)), p(s
2 (a))}, then T P (I 1 ) = {p(a), p(s
3 (a)), p(s
4 (a)), p(s
5 (a)), . . .}
and T P (I 2 ) = {p(a), p(s
4 (a)), p(s
5 (a)), . . .}. Thus, we have d r (I 1 , I 2 ) = 0 yet
d r (T P (I 1 ), T P (I 2 )) = 2
−2 , and therefore T P is not non-expansive. Next, consider powers I n = T
n (∅), the first few of which, as we have already seen, are as
P
follows: I 1 = B P , I 2 = {p(a)}, I 3 = B P \ {p(s(a))}, I 4 = {p(a), p(s
2 (a))}, I 5 =
B P \ {p(s(a)), p(s
3 (a))}, etc. Then we obtain that d r (I n , I n+1 ) takes value 0
if n is even and takes value 2
−n+1 if n is odd. Therefore, the sequence (I n )
is Cauchy and converges to I, say, in Q. By Proposition 3.3.5, we have that
(I n ) converges in Q to the set {p(a), p(s
2 (a)), p(s
4 (a)), . . .}, which therefore
coincides with I. It follows that I is a fixed point of T P , since T P is continuous in Q, and indeed I is the only fixed point of T P , as already noted in
Example 3.3.6.
4.6.18 Example Let P be the program
p(X) ← ¬q(X)
r(s(X)) ← r(X)
q(X) ← q(a), ¬r(X)
which is a slight modification of an example in [Apt et al., 1988, Page 97] and
is stratified. Again, T P is continuous relative to Q, but in this case T P is not
non-expansive for any choice of level mapping l and corresponding quasimetric
d r . To see this, put I 1 = {q(a)} and I 2 = T P (I 1 ) = {p(s(a)), p(s
2 (a)), . . .} ∪
{q(a), q(s(a)), . . .}. Then d r (I 1 , I 2 ) = 0 for any d r simply because I 1 ⊆ I 2 .
Since T P (I 2 ) = {q(a), q(s(a)), . . .}, we must have d r (T P (I 1 ), T P (I 2 )) > 0 for
any d r or in other words for any choice of l and corresponding d r , so that T P
is never non-expansive. Taking I = {r(a)} and setting I n = T
n (I), we have
P
I n = {r(s
n (a))}∪{p(a), p(s(a)), p(s
2 (a)), . . .}. Clearly, (I n ) is Cauchy (for any
choice of level mapping and corresponding d r ), and I n converges in Q to the
fixed point {p(a), p(s(a)), p(s
2 (a)), . . .}.
4.7 A Hierarchy of Fixed-Point Theorems
For the reader’s convenience, we have collected together in Table 4.3 the
main fixed-point theorems presented in this chapter, at least for single-valued
Mathematical Aspects of Logic Programming Semantics
4.6.17 Example Consider again the program P of Example 3.3.6
p(a) ←
p(s(X)) ← ¬p(X)
and note that P is not stratified nor even locally stratified. Define the level
mapping l on B P by l(p(s
n (a))) = n for each n. We note that in this
case T P is not non-expansive, for if we take I 1 = {p(a), p(s(a))} and I 2 =
{p(a), p(s(a)), p(s
2 (a))}, then T P (I 1 ) = {p(a), p(s
3 (a)), p(s
4 (a)), p(s
5 (a)), . . .}
and T P (I 2 ) = {p(a), p(s
4 (a)), p(s
5 (a)), . . .}. Thus, we have d r (I 1 , I 2 ) = 0 yet
d r (T P (I 1 ), T P (I 2 )) = 2
−2 , and therefore T P is not non-expansive. Next, consider powers I n = T
n (∅), the first few of which, as we have already seen, are as
P
follows: I 1 = B P , I 2 = {p(a)}, I 3 = B P \ {p(s(a))}, I 4 = {p(a), p(s
2 (a))}, I 5 =
B P \ {p(s(a)), p(s
3 (a))}, etc. Then we obtain that d r (I n , I n+1 ) takes value 0
if n is even and takes value 2
−n+1 if n is odd. Therefore, the sequence (I n )
is Cauchy and converges to I, say, in Q. By Proposition 3.3.5, we have that
(I n ) converges in Q to the set {p(a), p(s
2 (a)), p(s
4 (a)), . . .}, which therefore
coincides with I. It follows that I is a fixed point of T P , since T P is continuous in Q, and indeed I is the only fixed point of T P , as already noted in
Example 3.3.6.
4.6.18 Example Let P be the program
p(X) ← ¬q(X)
r(s(X)) ← r(X)
q(X) ← q(a), ¬r(X)
which is a slight modification of an example in [Apt et al., 1988, Page 97] and
is stratified. Again, T P is continuous relative to Q, but in this case T P is not
non-expansive for any choice of level mapping l and corresponding quasimetric
d r . To see this, put I 1 = {q(a)} and I 2 = T P (I 1 ) = {p(s(a)), p(s
2 (a)), . . .} ∪
{q(a), q(s(a)), . . .}. Then d r (I 1 , I 2 ) = 0 for any d r simply because I 1 ⊆ I 2 .
Since T P (I 2 ) = {q(a), q(s(a)), . . .}, we must have d r (T P (I 1 ), T P (I 2 )) > 0 for
any d r or in other words for any choice of l and corresponding d r , so that T P
is never non-expansive. Taking I = {r(a)} and setting I n = T
n (I), we have
P
I n = {r(s
n (a))}∪{p(a), p(s(a)), p(s
2 (a)), . . .}. Clearly, (I n ) is Cauchy (for any
choice of level mapping and corresponding d r ), and I n converges in Q to the
fixed point {p(a), p(s(a)), p(s
2 (a)), . . .}.
4.7 A Hierarchy of Fixed-Point Theorems
For the reader’s convenience, we have collected together in Table 4.3 the
main fixed-point theorems presented in this chapter, at least for single-valued