feldman@piccolo.cs.cornell.edu (Ronen Feldman) (07/13/90)
I have the following program which have exponential complexity, I want by a set of automatic transformations to get to an equivalent program with linear complexity. The original program: a(X) :- f1(X),f2(X). a(s(X)) :- b(X),a(X). b(X) :- f2(X),f3(X). b(s(X)) :- c(X),b(X). c(X) :- f3(X),f1(X). c(s(X)) :- a(X),c(X). The program I want to get as a result of some set of automatic transformations: a1(X) :- f1(X),f2(X),f3(X). a1(s(X)) :- a1(X). As far as I can see the programs are equivalent with respect to any query (provided that the f1,f2,f3 relations are the same for both programs). Does anyone see the transformations that can be applied to program1 so we can get program2? I thought about magic sets I don't see how it can produce program2. please email directly. Thanks Ronen Feldman (feldman@cs.cornell.edu)