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