Re: XML Encoding of XPath: Examples

[Murata Makoto <mura034@attglobal.net>]

> >In the tree case, we have a similar result.  The expression approach
> >such as XPath (and thus Schematron) and the automaton approach such
> >as RELAX and TREX are inherently equivalent.
> 
> I disagree. Sort of. They are equivalent only from a theoretical and
> reductionist view.

I have already proved equivalence in my paper.  Please read it.  

> As long as Xpaths are not as powerful as regexes by not having grouping or
> reptition, and as long as regexes do not allow full XPaths for particles,
> current grammar-based and path-based systems are not remotely equivalent in
> fact.

Right.  I did not say that XPath is as expressive as RELAX or TREX.  
I just said that the expression approach and the automaton (or gramamar) 
approach are inherently equivalent.

>And it is the higher-level abstractions which the schema uses to model
>things that give much of the value of language.  Schematron has no notion of
>type. XML Schemas has no equivalent to Schematron's pattern. To say
>"equivalent" may confuse people that the equivalence is the same equivalence
>as saying "C# is equivalent to Java" rather than "a C++ program is
>equivalent to its binary compiled form": equivalence does not mean
>equivalently useful or useable or congenial.

If you dislike the word "equivalent", I am happy to switch to "equally
expressive", "exactly capture", etc.  I use these phrases as a computer 
science term.

>For example, lets have a pattern called "three equal sized arrays in three
>documents" with the definition  "the number of children in element X in this
>document should be the same as the number of children of element Y in that
>document (URL given in the attribute @Y on the X element in this document)
>and it should be the same as the number of children of element Z in another
>document (URL given as the attribute @Z on the X element in this document)."

Regular expressions and automata are equally expressive when we use
their original definitions.  However, people have introduced many
mechanisms such as back references (which is your example) to regular
expressions.  I agree that such extension make regular expressions
more expressive than automata or grammars.  Nevertheless, automata and
grammars continue to be useful, and thus original regular expressions
remain important.  I am talking about such original regular
expressions.

Cheers,

Makoto