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 program is written in prolog but
the problem exist also for any other language that support recursion.
(so it is of interest to Lisp and ML people)
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).
An example for a query is a(s(s(s(c1)))) where f1(c1),f2(c1) and f3(c1) are
true. I claim that a1(X) = a(X) = b(X) = c(X) for every X.
(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 (·······@cs.cornell.edu)