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] Using The Principle of Least Power As A Razor

[ Lists Home | Date Index | Thread Index ]

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@metalab.unc.edu
XML in a Nutshell 3rd Edition Just Published!


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

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