Re: Blowout

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

> For TREX and RELAX, the latter question does have a decision
> procedure (not sure about Schematron).  For RELAX, the decision
> procedure "does any document match this schema" is O(M) in
> the size of the schema.  (In fact, it's probably O(1) -- I
> believe the answer is always "yes" in the case of RELAX.)
> 
> The satisfiability algorithm for TREX *is* worst-case
> exponential, due to <concur>, <interleave>, and <notAllowed>;
> however this doesn't say anthing about the time complexity of
> the validation algorithm (which is what TREX is _usually_
> used for).

This is not completely true. As usual, the devil is in the details.
How can you decide that the following datatype declaration does not
accept anything?

<simpleType name="myType">
  <restriction base="integer">
    <pattern value=".*x" />
  </restriction>
</simpleType>

Therefore in practice, it is impossible to compute the answer for "does
any set of bindings satisfy the formula?"




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