[xml-dev] Re: ID/IDREF makes XML generation NP-hard
by MURATA Makoto other posts by this author
Apr 3 2003 1:52PM messages near this date
Re: [xml-dev] Re: ID/IDREF makes XML generation NP-hard
|
[xml-dev] RELAX NG and datatypes make XML generation NP-hard
On 28 Mar 2003 21:59:11 +0000
ht@[...].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@[...].jp>
-----------------------------------------------------------------
The xml-dev list is sponsored by XML.org <http://www.xml.org> , an
initiative of OASIS <http://www.oasis-open.org>
The list archives are at http://lists.xml.org/archives/xml-dev/
To subscribe or unsubscribe from this list use the subscription
manager: <http://lists.xml.org/ob/adm.pl>
Thread:
Henry S. Thompson
Rick Jelliffe
Christian Nentwich
Murali Mani
Rick Jelliffe
Murali Mani
MURATA Makoto
Robert C. Lyons
Tim Bray
Murali Mani
|
