> > I've no idea what the theoretical limits of what you can do with a 
> > grammar are (I don't even know what the accepted definition of 
> > "grammar" is), but I
> 
> Err.  Murata-san has a very nice paper that characterizes the 
> sort of grammar embodied by several available grammars for 
> XML, including W3C XML Schema 

Thanks for the essay. I'm well aware that there's a vast theoretical
literature on different classes of grammar and their power. It doesn't alter
my point one bit - I'm not personally interested in exploring the limits of
the technology. There might well be a class of grammar in which I can
express the rule that February has 28 days except in a leap year, or that
the sales-to-date for a given month must be greater than the sales in the
previous month, but I can't see why I would want to express such constraints
grammatically when it's so much easier to express them in other ways.

>It's very likely that most W3C XML Schema parsers are implemented in this
fashion, rather than as 
>deterministic (or equivalently, nondeterministic) finite automata.  If that
*is* the case, then it seems >(to me) rather sensible to make use of the
power of that style of automata more fully, rather than 
>providing a sort of "escape" mechanism to break out of the automaton (which
effectively puts you into 
>turing machine territory, with an implementation problem of unknown
complexity).

Well, my implementation is a deterministic FSA, I can't speak for others.
But again that's not the point. The way users should express constraints
should be in the way that's most convenient and expressive for the users, it
has nothing to do with the capabilities of a particular piece of internal
technology. And predicate logic is hardly unknown territory. 

XPath, incidentally, is relationally complete but not Turing complete as far
as I know: unless you allow user-defined recursive functions you can't
express constraints like non-cyclicity of a graph. Though personally I have
no problems with allowing Turing-completeness in the validation language.
Users sometimes have to check that a parts explosion contains no cycles, and
they will find a language in which they can program such checks, however
much we try to stop them.

Michael Kay
http://www.saxonica.com/