Re: [xml-dev] Features of XML Languages that Increase Complexity?

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!

Cheers
Rick