W3C home > Mailing lists > Public > public-rif-wg@w3.org > December 2006

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

From: Gary Hallmark <GARY.HALLMARK@ORACLE.COM>
Date: Tue, 19 Dec 2006 00:02:49 -0700 (MST)
Message-ID: <16757505.1166511769129.JavaMail.oracle@rcsmt240.oracle.com>
To: Francis McCabe <frankmccabe@sandsoft.com>
Cc: public-rif-wg@w3.org 
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

attached mail follows:

Received on Tuesday, 19 December 2006 07:03:08 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 2 June 2009 18:33:34 GMT