RE: [xml-dev] Syntax versus Semantics (was: "vocabularyconstraints" and

["Costello, Roger L." <costello@mitre.org>]

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