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