Re: Shuffle automata

[Murata Makoto <mura034@attglobal.net>]

Kohsuke KAWAGUCHI wrote:

> 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?

bash-2.05$ ruby Validate.rb -automaton -debug abac.xml 
abac
start:0 
final:9 
0 -> <1, 5>
1 - a -> 2
2 -> 3
3 - b -> 4
<4, 8> -> 9
5 - a -> 6
6 -> 7
7 - c -> 8
:{0 <{1 }, {5 }> }
+{<{3 }, {5 }> <{1 }, {7 }> }
+{<{4 }, {5 }> }
+{<{4 }, {7 }> }
+{9 <{4 }, {8 }> }
Accept
bash-2.05$ 

Kohsuke KAWAGUCHI wrote:

> 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 keep track of both possibilities as usual.

Kohsuke KAWAGUCHI wrote:

> 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

Mine is ten times slower than jing.  But my program is written in ruby (an interepreted 
language)

Kohsuke KAWAGUCHI wrote:

> What it can't do is to efficiently handle expressions like (a? & ... &
> z?)*. Can the shuffle automata handle these expressions efficiently?

No.  I think that this is just difficult.

Cheers,

Makoto