[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Subject: Re: Shuffle automata
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]
Powered by eList eXpress LLC