Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!uunet!wuarchive!udel!sbcs!sbwarren!warren
From: warren@sbwarren.cs.sunysb.edu (David Scott Warren)
Newsgroups: comp.lang.prolog
Subject: Re: mutual recursion query
Message-ID: <9811@sbcs.sunysb.edu>
Date: 6 Jun 90 17:08:12 GMT
References: <4176@munnari.oz.au> <10462@spool.cs.wisc.edu> <718@fornax.UUCP> <3072@goanna.cs.rmit.oz.au> <3164@goanna.cs.rmit.oz.au>
Sender: news@sbcs.sunysb.edu
Organization: State University of New York at Stony Brook
Lines: 26

In <3164@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A.
O'Keefe) presents a Datalog example of a context-free grammar which
includes mutual recursions and asks:

>(If someone who is really at home with magic sets would care to explain
>what the magic sets method would do with this example I would be grateful.)

Not being an expert in magic sets, and at the risk of
oversimplifying, I will try to give my intuitions about magic sets
and grammars. 

The result of executing the ``Magic set''-transformed program
bottom-up (semi-naive) is essentially the same as Extension Table (or
OLDT) evaluation. (So one might think of Magic-sets as a
``compilation'' technique for extension tables.) And Extension Table
evaluation is essentially the same as Earley Deduction. And Earley
Deduction on Datalog grammars as Richard presented is Earley's
context-free recognition algorithm. So by transitivity of
``essentially the same as'', magic sets on Datalog grammars is Earley
recognition. Evidence for the validity of this claim is Raghu
Ramakrishnan's comment that under magic sets, left-recursion is
linear and right-recursion is quadratic, exactly as it is in Earley
recognition. 

David S. Warren
 warren@sbcs.sunysb.edu