What class of grammars is an =?UTF-8?Q?XPath=3F?=

[rjelliffe <rjelliffe@allette.com.au>]

 A correspondent recently asked me what formal class of grammars 
 Schematron schemas belonged to.

 He was interested, I gather, because I gather he expected to be able to 
 know what data structures would be needed for writing an implementation, 
 since the position in a Chomsky hierarchy can tell you the minimum class 
 of automaton.

 I told him first that I thought Schematron was not a useful fit in the 
 Chomsky hierarchy,  see
   
 http://broadcast.oreilly.com/2010/07/validating-operator-grammars-i.html

 (You could also say it was an indexed tree grammar implementable with a 
 branching automaton, perhaps.)

 Anyway, it is an interesting question. I think the same question could 
 be asked, rephrased, as "what is the smallest class of formal grammars 
 that every Xpath (evaluating to boolean) belongs to?"

 Anyone got any pointers or ideas on this? Pointers to any academic work 
 would be really interesting.

 Cheers
 Rick Jelliffe