Kohsuke KAWAGUCHI wrote:
> > I keep track of both possibilities as usual.
>
> Thank you. But if you keep all possibilities, then that might cause an
> combinatorial explosion.
Yes, it does. I don't think we can completely avoid it.
>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.
I have not implemented the shuffle closure operator, since RELAX NG does
not have it.
> Then what pattern can be efficiently handled by the new algorithm but
> not by the classic derivative-based algorithm?
Here is another bad news: I don't think that shuffle automata can be
used to compute the intersection, union, or difference of two patterns
of RELAX NG. I don't know how to prove (a* & b*) is equal to (a|b)*
However, I think that this new algorithm is important. First, it is
nice to have more than one algorithm. Second, in this algorithm, we
can create shuffle automata at compile time and can forget all patterns
at run time. Some people (including me) think that this is valuable.
Third, we have better understanding of interleaving and thus should
be able to design reasonable restrictions. Probably, the next step
is to consider boolean operations of shuffle languages.
Cheers,
Makoto
