OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

relax-ng message

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



[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Powered by eList eXpress LLC