Re: Shuffle automata

[Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>]

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