relax-ng message

Subject: Re: Issue: restrict <interleave>
From: Murata Makoto <mura034@attglobal.net>
To: relax-ng@lists.oasis-open.org
Date: Mon, 16 Jul 2001 22:30:52 +0900
Given words w, and w1, w2, ..., wn, is w in the interleaving of w1,


w2, ..., wn?  This problem is NP-complete ("Warmuth and Haussler,

Onthe Compexity of Iterated Shuffle, Journal of Computer and Syste
m
Sciences, 1984"
)
.

Jing is usually very fast, but I have some malic
ious
schemas/insta
n
ces.

0) Elaps
e
d 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 interle
a
ving6.xml

Elapsed time 60031 
m
illiseconds

c:\inter
l
eave>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
 i
nterleaving6.xm
l
Elapsed time 
1
00688 milliseconds

c
:
\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp jing.jar;c:\l
ib\jaxp.jar;c:\xerces-1
_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver interleavin
g6
2.rng interleaving6.xm
l
Elapse
d
 time 149391 millisecon
d
s

c:\interleave>jing.bat

c:\interleave>java -Xms50m -Xmx200m  -cp jing.j
ar;c:\lib\jaxp.jar;c:\xerces-1
_3_0\xerces.jar com.thaiopensource.relaxng.util.Driver inte
rl
eaving63.rng interleaving6.xm
l


Elapsed time 198359 mil
l
iseconds

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.Driv
e
r interleaving7.rng interleaving7
.
xml

Elapsed time 4
8
5375 milliseconds

1) interleaving6.rng

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

<element name="fo
o" xmlns="http:
//relaxng.or
g/ns/structure/0.9">
  <interleave>
    <group>
     <option
al><element name="a"><empty/></element></optional>
     <optio
nal><element name="b"><empty/></element></optional>
     <opti
onal><element name="c"><empty/></element></optional>
     <opt
ional><element name="d"><empty/></element></optional>
     <op
tional><element name="e"><empty/></element></optional>
     <o
ptional><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></optiona
l>
     <optional><element name="e"><empty/></element></option
al>
     <optional><element name="f"><empty/></element></optio
nal>
     <optional><element name="g"><empty/></element></opti
onal>
     <optional><element name="h"><empty/></element></opt
ional>
     <optional><element name="i"><empty/></element></op
tional>
    
 <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/></elemen
t></optional>
     <optional><element name="d"><empty/></eleme
nt></optional>
     <optional><element name="e"><empty/></elem
ent></optional>
     <optional><element name="f"><empty/></ele
ment></optional>
     <optional><element name="g"><empty/></el
ement></optional>
     <optional><element name="h"><empty/></e
lement></optional>
     <optional><element name="i"><empty/></
element></opt
ional>
    
 <optional><element name="j"><empty/></element></optional>
   
 </group>
    <group>
     <optional><element name="a"><empty
/></element></optional>
     <optional><element name="b"><empt
y/></element></optional>
     <optional><element name="c"><emp
ty/></element></optional>
     <optional><element name="d"><em
pty/></element></optional>
     <optional><element name="e"><e
mpty/></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/></e
lement></opt
ional>
     <optional><element name="j"><empty/></element></op
tional>
    </group>
    <group>
     <optional><element nam
e="a"><empty/></element></optional>
     <optional><element na
me="b"><empty/></element></optional>
     <optional><element n
ame="c"><empty/></element></optional>
     <optional><element 
name="d"><empty/></element></optional>
     <optional><element
 name="e"><empty/></element></optional>
     <optional><elemen
t name="f"><empty/></element></optional>
     <optional><eleme
nt name="g"><empty/></element></optional>
     <optional><elem
ent name="h"><empty/></element></optional>
     <optional><ele
ment name="i"
><empty/></elem
ent></optio
n
a
l>
     <optional><e
l
ement 
name=
"j"><
empty
/></e
lemen
t></o
ption
al>
    <
/grou
p>
 </
i
nterleave>
</element
>



2) interleaving6.xml

<foo>
<a/>
<b/>
<c/>
<d/>
<e/>

<f/>
<g/>
<
h/>
<i/>
<
j/>
</foo>

3) interleaving7.rng

<element name="foo" xmln
s="http://relaxng.org/ns/structure/0.9">
  <interleave>
    <
group>
     <optional><element name="a"><empty/></element></op
tional>
     <optional><element name="b"><empty/></element></o
ptional>
     <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/></elemen
t></optional>
     <optional><element name="h"><empty/></eleme
nt></optional>
     <optional><element name="i"><empty/></elem
ent></optiona
l>
     <op
tional><element name="j"><empty/></element></optional>
     <o
ptional><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"><empt
y/></element></optional>
     <optional><element name="f"><emp
ty/></element></optional>
     <optional><element name="g"><em
pty/></element></optional>
     <optional><element name="h"><e
mpty/></element></optional>
     <optional><element name="i"><
empty/></elem
ent></option
al>
     <optional><element name="j"><empty/></element></optio
nal>
     <optional><element name="k"><empty/></element></opti
onal>
    </group>
    <group>
     <optional><element name=
"a"><empty/></element></optional>
     <optional><element name
="b"><empty/></element></optional>
     <optional><element nam
e="c"><empty/></element></optional>
     <optional><element na
me="d"><empty/></element></optional>
     <optional><element n
ame="e"><empty/></element></optional>
     <optional><element 
name="f"><empty/></element></optional>
     <optional><element
 name="g"><empty/></element></optional>
     <optional><elemen
t name="h"><empty/></element></optional>
     <optional><eleme
nt name="i"><
empty/></ele
ment></optional>
     <optional><element name="j"><empty/></el
ement></optional>
     <optional><element name="k"><empty/></e
lement></optional>
    </group>
    <group>
     <optional><
element name="a"><empty/></element></optional>
     <optional>
<element name="b"><empty/></element></optional>
     <optional
><element name="c"><empty/></element></optional>
     <optiona
l><element name="d"><empty/></element></optional>
     <option
al><element name="e"><empty/></element></optional>
     <optio
nal><element name="f"><empty/></element></optional>
     <opti
onal><element name="g"><empty/></element></optional>
     <opt
ional><element name="h"><empty/></element></optional>
     <op
tional><eleme
nt 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></optiona
l>
     <optional><element name="h"><empty/></element></option
al>
     <op
tional><element
 name="i"><
e
m
pty/></element></opti
o
nal>
     
<opti
onal>
<elem
ent n
ame="
j"><e
mpty/
></el
ement
></op
tional>

  
   <optio
na
l><elem
ent 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
Follow-Ups:
- Re: Issue: restrict <interleave>
  - From: Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>