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

 


Help: OASIS Mailing Lists Help | MarkMail Help

 


 

   Re: ID/IDREF makes XML generation NP-hard

[ Lists Home | Date Index | Thread Index ]


On 28 Mar 2003 21:59:11 +0000
ht@cogsci.ed.ac.uk (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@hokkaido.email.ne.jp>






 

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS