Re: W3C RIF: "recursive rules" vs "recursive terms"

Doesn't cut just stop the DFS early?  So the average and worst case work of the prolog program is still O(size of the transitive closure), but a "goal directed" PR program only does O(size of the answer), which may be much, much less work.

This is a consequence of prolog's top-down vs. PR's bottom-up evaluation.  We are given a leaf *me*, so prolog still has to search to find the leaf, whereas the PR does not.

Cheers,
   Gary