OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
What class of grammars is an =?UTF-8?Q?XPath=3F?=

 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

 (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.

 Rick Jelliffe

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS