🚀 go-pugleaf

In article <3191@goanna.cs.rmit.oz.au>, ok@goanna.cs.rmit.oz.au (Richard A. O'Keefe) writes:
 ......
> Let me repeat the grammar, this time with the sequence arguments
> explicit, and one more rule which I accidentally forgot.
> 
> 	s(S0,S) :- np(P,N,nom,S0,S1), vp(P,N,S1,S).
> 
> 	np(P,N,C,S0,S) :- word(X,S0,S), pronoun(X,P,N,C).
> 	np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2),
> 			  noun(X,N), opt_rel(S2,S).
> 
> 	opt_rel(S0,S) :- word(that,S0,S1), vp(_,_,S1,S).
> 	opt_rel(S0,S) :- word(that,S0,S1), np(P,N,nom,S1,S2), tv(P,N,S2,S).
> 	opt_rel(S,S).
> 
> 	vp(P,N,S0,S) :- word(X,S0,S), intrans(X,P,N).
> 	vp(P,N,S0,S) :- tv(P,N,S0,S1), np(_,_,acc,S1,S).
> 
> 	tv(P,N,S0,S) :- word(X,S0,S), trans(X,P,N).
> 
> The rule which had been omitted lets us say "the rat that the cat chased"
> as well as "the cat that chased the rat", and it really made me look
> stupid leaving it out because the _point_ of my example was to show
> something that was naturally recurring in a "tree-structured" fashion.
> 
 ......

I am not an expert on natural language processing.  I am really sorry 
for not transforming fully your grammar into Prolog (the states S0, S1, 
etc. were missing).  Let me try this new set of rules.

The newly added rule makes the recursion not a single linear recursion 
but a multiple linear one.  

The "np" portion is transformed into a multiple linear recursion (without
mutually recursive predicates) as follows.

s(S0,S) :- np(P,N,nom,S0,S1), vp(P,N,S1,S).

np(P,N,C,S0,S) :- word(X,S0,S), pronoun(X,P,N,C).
np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S), noun(X,N).
np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), 
		word(that,S2,S3), word(Y,S3,S), intrans(Y,P,M).
np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), 
	word(that,S2,S3), word(Y,S3,S4), trans(Y,P,M), np(_,_,acc,S4,S).
np(3,N,_,S0,S) :- word(the,S0,S1), word(X,S1,S2), noun(X,N), 
	word(that,S2,S3), np(P,N1,nom,S3,S4), word(Y,S4,S), trans(Y,P1,N2).

Similarly for "vp" portion as well.

I understand the above "np" rule set as follows:

np(_,_) :- Pronoun(X).
np(3,_) :- "the", Noun(X).
np(3,_) :- "the", Noun(X), "that", Intrans(Y).
np(3,_) :- "the", Noun(X), "that", Trans(Y), np(_,acc).
np(3,_) :- "the", Noun(X), "that", np(_,nom), Trans(Y).

(Notice that in the real execution, we must associate it with all the 
proper states to make it complete.  3 means that all the generated Noun 
or Pronoun should be the third person, if my understanding is right).

As I discussed in my "Processing Multiple Linear Recursions" paper,
this multiple linear recursion cannot be evaluated by a transitive 
closure algorithm.  However, it can be evaluated by side-relation 
unioned processing.  We take the exit rule as

e :- [Pronoun(X)] U ["the", Noun(X)] U ["the", Noun(X), "that", Intrans(Y)].

and the left portions of the second linear recursive rule as

l2 :- "the", Noun(X), "that".

The rule set is equivelent to, (Sorry for further simplification,
we could associate more states but the results should be essentially
the same).

np(_) :- e.
np(_) :- l2, Trans(Y), np(acc).
np(_) :- l2, np(nom), Trans(Y).

The trick in the evaluation of this multiple linear recursion is that 
every time after we go through the portion ["the", Noun(X), "that"],
we set a flag [2].  If we go through one more portion [Trans(Y)], the 
flag is switched to [1].  Flag [1] should not have a matched Trans(Y)
after np(acc) but Flag [2] needs the match of a Trans(Y) after np(nom).
So the evaluation is quite close to the evaluation of a two-sided single
linear recursion (e.g., the same-generation problem).  That is, we may 
use the counting method or the magic sets method and treat it as if it 
were a single linear recursion.  This is another good example which
shows why deductive DB people want to study something beyond transitive 
closure (e.g. the same-generation recursion) in the evaluation of 
linear recursions.

This is a very interesting example.  Thanks.

-jiawei