
Chapter 14: Logic Programming and Parallel Complexity 559
4.
Bipartite transitive closure is defined using rule,
R(x,y) - R(x,y
1
),R(x
1
,y),R(x
1
,y
1
). With s(n) = 0(log η).
5.
If 0-ary IDB predicate R
c
is true, directed graph R
0
has a cycle,
R
c
— R(x,x). and R(x,y) — R(x,z),R(z,y). With s(n) = 0(log n).
6.
Context free language {a
n
cb
n
| n>0} is related to rule, R(x,y)
R
1
(x,z),R(z,z
1
),R
2
(z
1
,y). Here s(n) = Ω(η), but as we shall see this
query is in STAGE(log n).
7.
All tableaux queries can be trivially written in this language and are
bounded. It is possible to write less trivial programs, which are also
bounded. R(x,y) R(z,z,),R
1
(x,y),R
1
(z,z
1