[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: ID/IDREF makes XML generation NP-hard

• To: "Henry S. Thompson" <ht@c...>
• Subject: Re: ID/IDREF makes XML generation NP-hard
• From: Tim Bray <tbray@t...>
• Date: Sat, 29 Mar 2003 13:59:13 -0800
• Cc: xml-dev@l...
• In-reply-to: <f5badffqhjk.fsf@e...>
• References: <f5badffqhjk.fsf@e...>
• User-agent: Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.3) Gecko/20030312

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

• References:
  • ID/IDREF makes XML generation NP-hard
    • From: ht@c... (Henry S. Thompson)

• Prev by Date: Re: Re: If XML is too hard for a programmer, perhaps he'd be better off as a crossing guard
• Next by Date: RE: If XML is too hard for a programmer, perhaps he'd b e better off as a crossing guard
• Previous by thread: Re: ID/IDREF makes XML generation NP-hard
• Next by thread: RE: ID/IDREF makes XML generation NP-hard
• Index(es):
  • Date
  • Thread