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

Re: Using The Principle of Least Power As A Razor

• To: Rick Jelliffe <rjelliffe@a...>
• Subject: Re: Using The Principle of Least Power As A Razor
• From: Elliotte Harold <elharo@m...>
• Date: Tue, 21 Feb 2006 06:56:49 -0500
• Cc: XML Developers List <xml-dev@l...>
• In-reply-to: <43F4AF0F.8010308@a...>
• References: <15725CF6AFE2F34DB8A5B4770B7334EE0BB1FE99@h...> <3bb44c6e0602160816y6029709cr2081fb05aaeda59e@m...> <3bb44c6e0602160833l63f67a32x541c6d529fc8c113@m...> <43F4AF0F.8010308@a...>
• User-agent: Thunderbird 1.5 (Macintosh/20051201)

Rick Jelliffe wrote:

> My impression is that as soon as your schema language supports IDREF it 
> is stuffed,
> from an NP POV:  Schematron, XSD, RELAX NG, DTDs, the lot!

Why do you say that? Checking DTD-style IDREFs naively seems to be a 
linear problem: just read the document twice, once to find the IDREFs 
and once to find out whether anything matches them. Store the IDs and 
IDREFs in a couple of stacks as you go and you could do it in a single 
pass. Keep a counter for each IDREF to find out if it's matched more 
than once.

The process would seem to be linear in the size of the document; not at 
all NP-complete. What am I missing?


-- 
Elliotte Rusty Harold  elharo@m...
XML in a Nutshell 3rd Edition Just Published!
http://www.cafeconleche.org/books/xian3/
http://www.amazon.com/exec/obidos/ISBN=0596007647/cafeaulaitA/ref=nosim

• Follow-Ups:
  • Re: Using The Principle of Least Power As A Razor
    • From: Eric van der Vlist <vdv@d...>

• References:
  • RE: Using The Principle of Least Power As A Razor
    • From: "Bullard, Claude L (Len)" <len.bullard@i...>
  • Re: Using The Principle of Least Power As A Razor
    • From: bryan rasmussen <rasmussen.bryan@g...>
  • Re: Using The Principle of Least Power As A Razor
    • From: bryan rasmussen <rasmussen.bryan@g...>
  • Re: Using The Principle of Least Power As A Razor
    • From: Rick Jelliffe <rjelliffe@a...>

• Prev by Date: Sending an XML DOM Document to a webService
• Next by Date: RE: NMTOKENS: good or evil?
• Previous by thread: Re: Using The Principle of Least Power As A Razor
• Next by thread: Re: Using The Principle of Least Power As A Razor
• Index(es):
  • Date
  • Thread