relax-ng message

Subject: Re: Issue: restrict <interleave>
From: Murata Makoto <mura034@attglobal.net>
To: relax-ng@lists.oasis-open.org
Date: Tue, 17 Jul 2001 09:50:07 +0900
Kohsuke KAWAGUCHI wrote:

> 
> It seems to me that there are lot of unnecessary line breaks in your
> post and therefore it's hard to read.

Sorry.  Hopes this works.

Cheers,

Makoto
-----------------------------------------------------------------------------------------------

Given words w, and w1, w2, ..., wn, is w in the interleaving of w1,
w2, ..., wn?  This problem is NP-complete ("Warmuth and Haussler, On
the Compexity of Iterated Shuffle, Journal of Computer and System
Sciences, 1984" ) .

Jing is usually very fast, but I have some malicious
schemas/instances which causes explosion.

0) Elapsed time

c:\interleave>java -Xms50m -Xmx200m  -cp
jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar
com.thaiopensource.relaxng.util.Driver
interleaving6.rng interleaving6.xml

Elapsed time 60031 milliseconds

c:\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp
jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar 
com.thaiopensource.relaxng.util.Driver
interleaving61.rng interleaving6.xml

Elapsed time 100688 milliseconds

c:\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp
jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar
com.thaiopensource.relaxng.util.Driver
interleaving62.rng interleaving6.xml

Elapsed time 149391 milliseconds

c:\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp
jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar
com.thaiopensource.relaxng.util.Driver
interleaving63.rng interleaving6.xml

Elapsed time 198359 milliseconds

c:\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp
jing.jar;c:\lib\jaxp.jar;c:\xerces-1_3_0\xerces.jar
com.thaiopensource.relaxng.util.Driver
interleaving7.rng interleaving7.xml

Elapsed time 485375 milliseconds

1) interleaving6.rng

interleaving61.rng, interleaving62.rng, and interleaving63.rng has one,
 two, and three more <group>s, respectively.


<element name="foo" xmlns="http://relaxng.org/ns/structure/0.9">
  <interleave>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
    </group>
 </interleave>
</element>

2) interleaving6.xml

<foo>
<a/>
<b/>
<c/>
<d/>
<e/>
<f/>
<g/>
<h/>
<i/>
<j/>
</foo>



3) interleaving7.rng

<element name="foo" xmlns="http://relaxng.org/ns/structure/0.9">
  <interleave>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
     <optional><element name="k"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
     <optional><element name="k"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
     <optional><element name="k"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
     <optional><element name="k"><empty/></element></optional>
    </group>
    <group>
     <optional><element name="a"><empty/></element></optional>
     <optional><element name="b"><empty/></element></optional>
     <optional><element name="c"><empty/></element></optional>
     <optional><element name="d"><empty/></element></optional>
     <optional><element name="e"><empty/></element></optional>
     <optional><element name="f"><empty/></element></optional>
     <optional><element name="g"><empty/></element></optional>
     <optional><element name="h"><empty/></element></optional>
     <optional><element name="i"><empty/></element></optional>
     <optional><element name="j"><empty/></element></optional>
     <optional><element name="k"><empty/></element></optional>
    </group>
 </interleave>
</element>








4) interleaving7.xml

<foo>
<a/>
<b/>
<c/>
<d/>
<e/>
<f/>
<g/>
<h/>
<i/>
<j/>
<k/>
</foo>


Cheers,

Makoto
References:
- Re: Issue: restrict <interleave>
  - From: Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>