[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Shuffle automata
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC