Re: Issue: restrict <interleave>

[James Clark <jjc@jclark.com>]

Some sort of restriction on interleave is a good idea, but figuring out 
exactly the right restriction seems a hard problem to me. I think we need 
more implementation experience, particularly in implementing subsumption. 
For the moment, I think we should say in the spec that we plan to impose a 
restriction and ask for feedback on what the restriction should be.

--On 26 June 2001 11:02 +0900 MURATA Makoto <mura034@attglobal.net> wrote:

> Summary: Although <interleave> is useful, it causes problems to
> automata-based  validation.  Some restrictions are strongly required.
>
>
> <interleave> cannot be translated to string automata without causing
> combinatory  explosion.  For example, consider
>
> <interleave>
>   <ref name="a"/>
>   <ref name="b"/>
> ...
>   <ref name="y"/>
>   <ref name="z"/>
> </interleave>
>
> If we construct an automaton, we need 2^28 -1 states.
>
> Traditionally, validation has been done by constructing string automata
> for  content models or tree automata for the entire schema.  Since such
> construction is  still important, RELAX NG should make it possible.  At
> present, <interleave> is  the only construct that makes such construction
> impossible.
>
> One useful restriction is as follows:
>
> 1) <interleave> appear as direct subordinates of <element>, other
> <interleave>,  or combine="interleave"
>
> 2) subpatterns of <interleave> are overlapping; that is, given a start
> tag and  <interleave>pattern1 pattern2</interleave>, we can determine
> which pattern  to choose.
>
> Note: 1) can be relaxed by allowing <interleave> to occur as direct
> subordinates  of <choice>, which is in turn subordinate to <element>,
> possibly via other  <choice> elements.
>
> Cheers,
>
> Makoto
>
> ------------------------------------------------------------------
> To unsubscribe from this elist send a message with the single word
> "unsubscribe" in the body to: relax-ng-request@lists.oasis-open.org
>
>