OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Re: [xml-dev] Features of XML Languages that Increase Complexity?

I am sure Roger will be happy to know that if someone implements XML as a conforming SGML system, implementing the SGML Declaration at
then they are limited to  99,999,999 characters, which is the maximum that SGML allowed (or something like that: TOTALCAP).   AFAIK XML documents with this restriction would be
of the theoretical class recursive rather then recusively enumerable.

But to a more general point, the problem underlying Rogers comments are, I think, that considering documents using language-theoretic ideas is
probably not as useful as it may appear:

Take problem 4 above.  If we have a document (i.e. it is sitting, finite, in memory), then finding out whether an IDREF matches an ID is an linear  O(n) operation (2 passes).

In a way, this gives us a two-stage grammar:  an upper language (the document is a sequence of bytes that must fit into virtual memory) and a low language (XML or
whatever) where the first language excludes infinite documents, and some of the theoretical characteristics that attach to them.

SGML allowed a document to state how much capacity it required, and for an implementation to state what capacity it provided: for example, for the number of attribute it could handle.
This is a relic of 1980s capacities, but it is amazing that 30 years later there are still issues in the same kind of area!


[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

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

Copyright 1993-2007 XML.org. This site is hosted by OASIS