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

# relax-ng message

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

Subject: Re: Shuffle automata

• From: Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>
• To: relax-ng@lists.oasis-open.org
• Date: Mon, 23 Jul 2001 12:17:40 -0700

```
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]