[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? ((a+)!)! 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? regards, -- 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