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
