%query: q(i,i). %From sagiv Tue Jan 7 10:56:23 1992 %Received: by humus.huji.ac.il (5.65b+IDA/HU-4.7) % id AA16201; Tue, 7 Jan 92 10:56:22 +0200 %From: yehoshua Sagiv <sagiv> %Date: Tue, 7 Jan 92 10:56:22 +0200 %Message-Id: <9201070856.AA16201@humus.huji.ac.il> %To: naomil %Subject: example %Status: R %Following is an example that is referred to in footnote 4. %It is due to Allen Van Gelder (originally, I gave another example, but %Allen pointed out that his algorithm could handle it by first applying %unfolding; later Allen emblished my original example to the following one %and showed that unfolding does not help his method in this case). %Note that in the following example there is a cycle involving q, p, r, t, %and q again,such that nothing gets smaller along that cycle. e(a,b). q(X,Y) :- e(X,Y). q(X,f(f(X))) :- p(X,f(f(X))), q(X,f(X)). q(X,f(f(Y))) :- p(X,f(Y)). p(X,Y) :- e(X,Y). p(X,f(Y)) :- r(X,f(Y)), p(X,Y). r(X,Y) :- e(X,Y). r(X,f(Y)) :- q(X,Y), r(X,Y). r(f(X),f(X)) :- t(f(X),f(X)). t(X,Y) :- e(X,Y). t(f(X),f(Y)) :- q(f(X),f(Y)), t(X,Y). %---Shuky Sagiv
content may be truncated. 'popout' for larger text window.
