OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

relax-ng message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Subject: Re: Shuffle automata

> > Consider the instance "abac". First, the root marker is "forked" to q1
> > and q4. Then, you have a choice of moving q1 or moving q4. How can you
> > decide which one to move?
> I keep track of both possibilities as usual.

Thank you. But if you keep all possibilities, then that might cause an
combinatorial explosion. How about the following?


where X! denotes the shuffle closure of X. Because for each "a", the
algorithm has a choice of either creating a new marker or advancing an
existing marker. If it chooses to create a new marker, then there is a
choice of which marker to use as the parent of the new marker.

> > Without this, I don't think this algorithm can handle examples you
> > showed in http://lists.oasis-open.org/archives/relax-ng/200107/msg00185.html
> Mine is ten times slower than jing.  But my program is written in ruby (an interepreted 
> language)
> > What it can't do is to efficiently handle expressions like (a? & ... &
> > z?)*. Can the shuffle automata handle these expressions efficiently?
> No.  I think that this is just difficult.

Then what pattern can be efficiently handled by the new algorithm but
not by the classic derivative-based algorithm?

Kohsuke KAWAGUCHI                          +1 650 786 0721
Sun Microsystems                   kohsuke.kawaguchi@sun.com

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Powered by eList eXpress LLC