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