Re: New XSL Optimization

Subject: Re: New XSL Optimization
From: S Manimaran <mani@xxxxxxxxxxxxxxxxx>
Date: Thu, 1 Jul 1999 02:41:56 +0530 (IST)
Hi,

On Fri, 25 Jun 1999, The XSL-List Digest wrote:

> ------------------------------
> From: Paul Prescod <paul@xxxxxxxxxxx>
> Subject: Re: New XSL Optimization
> 
> S Manimaran wrote:
> > 
> > 1. First I extracted out the match patterns to be matched from the XSL
> > stylesheet. Then the match patterns are converted to a context-free
> > grammar whose language is the matching trees in pre-order linearized form.
> 
> 
> You can do much better if you do not use a context free grammar and
> instead use a regular tree grammar. Context free grammars are way, way,
> way, more general than anything you can find in an XML document. Therefore
> your algorithm (Earley) is more general than needed.
> 
> See http://www.prescod.net/forests/shorttut
> 

	Many thanks for pointing out this. Yes, now I also feel regular
tree grammars will make things easier, and the performance of the pattern
matcher will improve very much if regular tree grammars are used instead
of CFG.
	Now I am planning to make the XSL patterns as regular tree
grammars instead of CFG, and use a one pass algorithm for doing pattern
matching using Push Down Forest Automata as mentioned in the paper by
Andreas Neumann and Helmut Seidl titled "Locating Matches of Tree Patterns
in Forests". This paper can be found at 
"http://www.informatik.uni-trier.de/~neumann/Papers/fsttcs98.ps.gz";
"http://www.informatik.uni-trier.de/~neumann/Papers/index-e.html";

	Is there any tool existing for pattern matching using Regular
Tree Grammars? Can anyone suggest me some reference, where I can possibly
get some tools for implementing Push Down Forest Automata or any Tree
Automata.

Thanks, (Merci beaucoup)
-S.Manimaran,

-------------------------------------------------------------------------------
URL::http://www2.csa.iisc.ernet.in/~mani/
Indian Internet Chess Server IICS::telnet 144.16.67.53 5000
Join frenchlist by sending a mail to french@xxxxxxxxxxxxxxxxx
f16    Fingerprint16 = EC FF 4D 6C 3A 09 84 30  AA B5 F0 A2 38 A0 4C A4


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


Current Thread