[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Blowout

• From: Kohsuke KAWAGUCHI <k-kawa@b...>
• To: Joe English <jenglish@f...>
• Date: Mon, 05 Mar 2001 10:19:06 -0800

> 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@b...

• References:
  • Re: Blowout
    • From: ht@c... (Henry S. Thompson)
  • Re: Blowout
    • From: Joe English <jenglish@f...>

• Prev by Date: Re: Fw: RSS 1.0 vs. RSS 0.9*
• Next by Date: The devil is always in the detail...
• Previous by thread: Re: Blowout
• Next by thread: Re: Blowout
• Index(es):
  • Date
  • Thread