RE: [xml-dev] ID/IDREF makes XML generation NP-hard
by Bullard, Claude L (Len) other posts by this author
Mar 28 2003 10:41PM messages near this date
Re: [xml-dev] If XML is too hard for a programmer, perhaps he'd b e better off as a crossing guard
|
Re: [xml-dev] ID/IDREF makes XML generation NP-hard
That's neat, Henry, and I don't mean to be mean-spirited,
but is this a "so, but so what?" kind of thing to know?
len
-----Original Message-----
From: ht@[...].uk [mailto:ht@[...].uk]
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.
-----------------------------------------------------------------
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:
Bullard, Claude L (Len)
Henry S. Thompson
|
