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


Help: OASIS Mailing Lists Help | MarkMail Help

relax-ng message

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Subject: ID/IDREF problem

I'd like to bring up the problem of ID and IDREF. ID and IDREF are very
problematic for validating processor.

Is there any plan to add some constraint to TREX to avoid this problem?
Or should processors be capable of handling this?

Consider the following grammar.

<element name="root">
    <!-- foo of ID/IDREF -->
    <element name="foo">
      <attribute name="id" type="ID" />
      <attribute name="ref" type="IDREF" />
    <!-- foo of string/string pair -->
    <element name="foo">
      <attribute name="id" type="string" />
      <attribute name="ref" type="string" />

How can you decide that which "foo" is applicable? You have to decide,
otherwise IDREF cannot be validated.

Example instance:

  <foo id="x" ref="notDefinedSoThisMustBeString" />
  <foo id="x" ref="y" />
  <foo id="y" ref="x" />

This problem (ID/IDREF problem) can be polynomial-reducible from the
satisfiability problem of boolean logic, which is NP-complete. So in
worst case, validation takes exponential time to the size of the

E-Mail: k-kawa@bigfoot.com

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [Elist Home]

Powered by eList eXpress LLC