Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cornell!feldman
From: feldman@piccolo.cs.cornell.edu (Ronen Feldman)
Newsgroups: comp.lang.prolog
Subject: mutual recursion elimination
Message-ID: <43267@cornell.UUCP>
Date: 12 Jul 90 22:01:01 GMT
Sender: nobody@cornell.UUCP
Reply-To: feldman@cs.cornell.edu (Ronen Feldman)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 42

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)