[
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>
|
