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

 


Help: OASIS Mailing Lists Help | MarkMail Help

relax-ng message

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


Subject: Issue: restrict <interleave>


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


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


Powered by eList eXpress LLC