[
Lists Home |
Date Index |
Thread Index
]
From: "Murali Mani" <mani@CS.UCLA.EDU>
>
> 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
> (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>
>
>
|
