Lists Home |
Date Index |
On 28 Mar 2003 21:59:11 +0000
firstname.lastname@example.org (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
MURATA Makoto <email@example.com>