ID/IDREF problem

[Kohsuke KAWAGUCHI <kohsuke.kawaguchi@eng.sun.com>]

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">
  <choice>
    <!-- foo of ID/IDREF -->
    <element name="foo">
      <attribute name="id" type="ID" />
      <attribute name="ref" type="IDREF" />
    </element>
    
    <!-- foo of string/string pair -->
    <element name="foo">
      <attribute name="id" type="string" />
      <attribute name="ref" type="string" />
    </element>
  </choice>
</element>

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


Example instance:

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


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
instance.


regards,
----------------------
K.Kawaguchi
E-Mail: k-kawa@bigfoot.com