Re: Shuffle automata

[Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>]

> > 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