Hi Folks,

Michael Kay wrote: 

> We're talking here about rules for 
> deciding statically whether a document 
> is or is not a member of some set of 
> valid documents

What does it mean to "statically decide"?


> I would suggest one might classify the 
> validity rules according to the 
> computational power needed to express 
> them:

... computational power  needed to <<express>> them

Do you mean: 

... computational power needed to <<evaluate>> them

That is, do you mean "evaluate" or "express"?
 

Categories:

> (a) those rules that can be expressed using regular expressions
> 
> (b) those rules that can be expressed in BNF
> 
> (c) those rules that can be expressed in first-order 
> predicate calculus
> (e.g. XPath 2.0)
> 
> (d) those rules that can only be evaluated using a Turing machine.

Here I rephrase the categories using the term "evaluate" rather than "express":

(a) Those rules that can be evaluated using a computer that has the power to evaluate regular expressions.

(b) Those rules that can be evaluated using a computer that has the power to evaluate BNF expressions.

(c) Those rules that can be evaluated using a computer that has the power to evaluate first-order predicate calculus (e.g. XPath 2.0) expressions. 

(d) Those rules that can only be evaluated using a Turing machine.

Do these faithfully express what you mean?


> > XSD 1.1 gives us (a) and (c).

Isn't (b) just grammar rules, e.g.

  The Book element shall contain a sequence of 
  Title, Author, Date, ISBN, and Publisher elements


This is fascinating:

    A thing can be categorized as in the realm 
    of "syntax" based on how much computing 
    power is required to evaluate it.


/Roger
_______________________________________________________________________

XML-DEV is a publicly archived, unmoderated list hosted by OASIS
to support XML implementation and development. To minimize
spam in the archives, you must subscribe before posting.

[Un]Subscribe/change address: http://www.oasis-open.org/mlmanage/
Or unsubscribe: xml-dev-unsubscribe@l...
subscribe: xml-dev-subscribe@l...
List archive: http://lists.xml.org/archives/xml-dev/
List Guidelines: http://www.oasis-open.org/maillists/guidelines.php