OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Blowout

> 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" />

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

E-Mail: k-kawa@bigfoot.com