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

*From*:**Kohsuke KAWAGUCHI <k-kawa@bigfoot.com>***To*: Joe English <jenglish@flightlab.com>*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@bigfoot.com

**References**:**Re: Blowout***From:*ht@cogsci.ed.ac.uk (Henry S. Thompson)

**Re: Blowout***From:*Joe English <jenglish@flightlab.com>

- 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):