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

Re: ID/IDREF makes XML generation NP-hard

• To: ht@c... (Henry S. Thompson)
• Subject: Re: ID/IDREF makes XML generation NP-hard
• From: MURATA Makoto <murata@h...>
• Date: Thu, 03 Apr 2003 22:52:02 +0900
• Cc: xml-dev@l...
• In-reply-to: <f5badffqhjk.fsf@e...>
• References: <f5badffqhjk.fsf@e...>

On 28 Mar 2003 21:59:11 +0000
ht@c... (Henry S. Thompson) wrote:

> Somewhat surprisingly, it turns out that answering the question, for an
> arbitrary XML DTD, "Are there any valid instances of the document type
> defined by this DTD?", is an NP-hard problem.

A similar result was shown by:

On XML Integrity Constraints in the Presence of DTDs
Journal of the ACM (JACM), Volume 49 , Issue 3, pp 368 - 406, May 2002.
Wenfei Fan and Leonid Libkin

http://www.bell-labs.com/user/wenfei/papers/jacm.pdf

-- 
MURATA Makoto <murata@h...>

• Follow-Ups:
  • Re: Re: ID/IDREF makes XML generation NP-hard
    • From: "Rick Jelliffe" <ricko@a...>

• Prev by Date: Re: Unicode normalization in XML 1.1
• Next by Date: RE: CDATA
• Previous by thread: RELAX NG and datatypes make XML generation NP-hard
• Next by thread: Re: Re: ID/IDREF makes XML generation NP-hard
• Index(es):
  • Date
  • Thread