Re: ID/IDREF makes XML generation NP-hard
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/)
PURCHASE STYLUS STUDIO ONLINE TODAY!
Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!
Download The World's Best XML IDE!
Accelerate XML development with our award-winning XML IDE - Download a free trial today!
Subscribe in XML format