[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: xPath 2.0, XSLT 2.0 ... size increase over v1.0

• To: Bob Foster <bob@o...>
• Subject: Re: xPath 2.0, XSLT 2.0 ... size increase over v1.0
• From: Murali Mani <mani@C...>
• Date: Thu, 12 Jun 2003 12:57:59 -0700 (PDT)
• Cc: <xml-dev@l...>
• In-reply-to: <0dbf01c330b8$1d8fb9a0$1401a8c0@snobird>

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

• Follow-Ups:
  • RE: xPath 2.0, XSLT 2.0 ... size increase over v1.0
    • From: "Michael Kay" <michael.h.kay@n...>

• References:
  • Re: xPath 2.0, XSLT 2.0 ... size increase over v1.0
    • From: "Bob Foster" <bob@o...>

• Prev by Date: RE: XML Indirection Facility
• Next by Date: high speed Web services binary attachment protocol
• Previous by thread: Re: xPath 2.0, XSLT 2.0 ... size increase over v1.0
• Next by thread: RE: xPath 2.0, XSLT 2.0 ... size increase over v1.0
• Index(es):
  • Date
  • Thread