Cart
[Home] [By Thread] [By Date] [Recent Entries]
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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] |
