OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help



   Re: [xml-dev] ID/IDREF makes XML generation NP-hard

[ Lists Home | Date Index | Thread Index ]

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


<!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/)


News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 2001 XML.org. This site is hosted by OASIS