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

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



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?

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