[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message] The devil is always in the detail...
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@b...
|
PURCHASE STYLUS STUDIO ONLINE TODAY!Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced! Download The World's Best XML IDE!Accelerate XML development with our award-winning XML IDE - Download a free trial today! Subscribe in XML format
|