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.

There's related problem that I'm willing to bet is as well.  Suppose you 
take an instance and generate a trivial DTD for it by making one 
<!ELEMENT declaration for every actual element.  For example

<x> 
   <y> <a/><a/><a/></y>
   <y> <a/><a/></y>
   </x> 
generates

<!ELEMENT x (y,y)> 
<!ELEMENT y (a,a,a)> 
<!ELEMENT y (a,a)> 

The problem is to reduce the grammar to a  minimal form by the 
application of Kleene * and +.  E.g.

<!ELEMENT x (y+)> 
<!ELEMENT y (a+)> 

I think there's a fistful of dissertations lurking in there, and last 
time I checked (admittedly a decade or more ago) it hadn't been worked 
over very well.
-- 
Cheers, Tim Bray
         (ongoing fragmented essay: http://www.tbray.org/ongoing/)



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