The devil is always in the detail...

[Kohsuke KAWAGUCHI <k-kawa@bigfoot.com>]

Without proper restriction of the use of ID/IDREF, it is possible for the
validation algorithm to be as complex as NP-hard.

Here is the shortened version of your example:

>  (a v b v ~c) ^  (~b v d v ~e) 

Consider the following instance

<termRef idref="t1" />
<termRef idref="t2" />

<varRef idref="a" />
<varRef idref="b" />
<varRef idref="c" />
  ...

<var id="a" idref="a.true" />
<var id="a" idref="a.false" />
<var id="b" idref="b.true" />
<var id="b" idref="b.false" />
  ...

<term id="t1" idref="a.true" />
<term id="t1" idref="b.true" />
<term id="t1" idref="c.false" />

<term id="t2" idref="b.false" />
<term id="t2" idref="d.true" />
<term id="t2" idref="e.false" />


And the grammar G at the bottom of this post (note that RELAX has
restriction over the use of ID/IDREF and thus the following grammar is
not a valid RELAX module).

Basically, the following grammar "chooses" one <term> among those which share
the same id value, and one <var> among those which share the same id
value. Only attributes of selected ones are considered as ID/IDREF pair
and others are considered as string.

And if this instance is valid, it means we have a biding of variables
that satisfies the original boolean expression. If this instance is
invalid, then we don't have one.

And as you can see, this encoding can be done in linear time.

Therefore, 3SAT is polynomial-time reducible to the problem of
validation.

I believe TREX does not have any constraint in the use of ID/IDREF. If
so, validation of TREX takes exponential time/space in the worst case.



<elementRule role="termRef">
  <tag />
  <attribute name="idref" type="IDREF" />
</elementRule>
<elementRule role="varRef">
  <tag />
  <attribute name="idref" type="IDREF" />
</elementRule>

<elementRule role="var">
  <tag />
  <attribute name="id" type="ID" />
  <attribute name="idref" type="IDREF" />
</elementRule>
<elementRule role="var">
  <tag />
  <attribute name="id" type="string" />
  <attribute name="idref" type="string" />
</elementRule>

<elementRule role="term">
  <tag />
  <attribute name="id" type="ID" />
  <attribute name="idref" type="IDREF" />
</elementRule>
<elementRule role="term">
  <tag />
  <attribute name="id" type="string" />
  <attribute name="idref" type="string" />
</elementRule>




regards,
----------------------
K.Kawaguchi
E-Mail: k-kawa@bigfoot.com