← Prev in month ← Prev in thread

Issue: restrict <interleave>

From
MURATA Makoto <>
Date
2001-06-26T06:53:04+00:00
ID
Thread
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
← Prev in month ← Prev in thread