[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Shuffle automata
I read the first paper, "Shuffle languages are in P". However, I was unable to understand several things. How does it handle ambiguous interleave, like (a,b)&(a,c) ? The shuffle automaton for this expression would be q0 -> <q1,q4> q1 -a-> q2 -b-> q3 q4 -a-> q5 -c-> q6 <q3,q6> -> qf 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 tried to find the answer in the paper, but all I could find is the final sentence in the section 6: In each step M guesses the next configuration C_i, transition to be taken t_i, .... Well, how can we "guess" it? 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 RegExp-derivative algorithm vs Shuffle Automata =============================================== You wrote > I have implemented it. My implementation can handle (a? & b? & ... & z?). but the regular expression-derivative algorithm used in Jing is also capable of efficiently handling (a? & b? & c? & ... & z?). What it can't do is to efficiently handle expressions like (a? & ... & z?)*. Can the shuffle automata handle these expressions efficiently? regards, -- Kohsuke KAWAGUCHI +1 650 786 0721 Sun Microsystems kohsuke.kawaguchi@sun.com
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC