[
Lists Home |
Date Index |
Thread Index
]
On Thu, 12 Jun 2003, Bob Foster wrote:
> > Regarding mathematical properties: in particular, closure properties.
> >
> > The operations being closed under regular tree languages might be
> > desirable property..
> >
> > I have seen two kinds of operations under which regular tree languages are
> > not closed.. that is the result is not a regular tree language..
> >
> > (a) Consider the schema:
> > S -> s (A, S, B) | s ()
> > A -> a ()
> > B -> b ()
> >
> > if we write a query like // (a | b) -- the result is (a^n b^n) which is
> > not regular tree language..
>
> The result is not a tree, it is a sequence (a()^n, b()^n). The result is not
> a property of the query but of the schema. The schema, a regular tree
> grammar, describes the derivation tree of the context-free language:
>
> s ->
> s-> a s b
>
> where s is non-terminal and a,b are terminals, which is the set of strings
> a^n, b^n, n >= 0. So it is not surprising that the query result sequence is
> the same set of strings.
>
> Bob
It is correct that the given schema describes the derivation tree set of a
context free grammar.
At the same time, I can also argue that if we do not allow | or element
construction the result will be regular, right? But this cannot be
solution also - because we need | operator.. but do we need element
construction in XPath??
thanks and regards - murali.
> > (b) Consider
> > S -> s (A*)
> > A -> a ()
> >
> > consider the query
> > for $x in //a
> > return <b/>
> > for $x in //a
> > return <c/>
> >
> > the result is (b^n c^n)
> >
> > The question is has the new constructs in XPath made it not closed or
> > not.. It might have.. If someone has studied these aspects, then we can
> > know if XPath 2.0 is different from XPath 1.0 in these respects also..
> >
> > cheers and regards - murali.
> >
> >
> > -----------------------------------------------------------------
> > The xml-dev list is sponsored by XML.org <http://www.xml.org>, an
> > initiative of OASIS <http://www.oasis-open.org>
> >
> > The list archives are at http://lists.xml.org/archives/xml-dev/
> >
> > To subscribe or unsubscribe from this list use the subscription
> > manager: <http://lists.xml.org/ob/adm.pl>
> >
> >
>
|
