Path: utzoo!attcan!uunet!cs.utexas.edu!asuvax!noao!arizona!debray
From: debray@cs.arizona.edu (Saumya K. Debray)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Summary: transitive closures
Message-ID: <21907@megaron.cs.arizona.edu>
Date: 7 Jun 90 13:01:35 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3164@goanna.cs.rmit.oz.au>
Organization: U of Arizona CS Dept, Tucson
Lines: 19

Richard A. O'Keefe (ok@goanna.cs.rmit.oz.au) writes:

> In article <718@fornax.UUCP>, han@fornax.UUCP (Jiawei Han) wrote
> in response to my question about transforming mutual recursion.
> The bottom line was that transforming mutual recursion into linear
> recursion permits the use of a transitive closure algorithm.
> 
> The question is, when is this a good idea?

This is probably tangential to Richard's point, but there are transitive
closure algorithms that require O(log N) iterations to compute the
fixpoint, where the (semi)naive algorithm for fixpoint computation would
require O(N) iterations.  (There is, however, some growth in code size.:-)

-- 
Saumya Debray		CS Department, University of Arizona, Tucson

     internet:   debray@cs.arizona.edu
     uucp:       uunet!arizona!debray