Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!linus!philabs!seismo!hao!hplabs!sri-unix!Abbott@AeroSpace
From: Abbott@AeroSpace@sri-unix.UUCP
Newsgroups: net.lang.prolog
Subject: Transitive Closures
Message-ID: <11903@sri-arpa.UUCP>
Date: Sat, 17-Sep-83 16:01:00 EDT
Article-I.D.: sri-arpa.11903
Posted: Sat Sep 17 16:01:00 1983
Date-Received: Mon, 26-Sep-83 07:48:48 EDT
Lines: 28

From:  Abbott at AeroSpace ( Russ Abbott )

The recent discussion of transitive relations has drifted somewhat
from the original question.  I thought this might be a good time to
raise it again.

Does anyone know of a good way to write a predicate in Prolog that
defines a relation to be the transitive closure of another relation.
For example:

        transitive_closure(R, T_R).

should have the side-effect of ensuring that if R(a, b) and R(b, c)
are either in the database or ( important! ) are added to the database
later, then T_R(X, Y) will succeed with (X, Y) being bound to (a, b),
(b, c), and (a, c) in turn.

One might imagine writing something like:

transitive_closure(R, T_R) :-
        assert((
                T_R(A, C) :-
                        R(A, C);
                                T_R(A, B), T_R(B, C)
                                                )).

But that leads to various difficulties involving infinite recursion.
So far, there are no clean solutions.