W3C home > Mailing lists > Public > www-xml-schema-comments@w3.org > October to December 2000

Comment about recursive group definition

From: Murali Mani <mani@CS.UCLA.EDU>
Date: Thu, 12 Oct 2000 09:13:11 -0700 (PDT)
To: www-xml-schema-comments@w3.org
Message-ID: <Pine.SOL.4.10.10010120901200.20937-100000@panther.cs.ucla.edu>

Hi,

I was reading the Sept draft of XML Schema, and I had a general
comment/question. I believe this was overlooked by the schema WG.

XML Schema Part 1: Structures: Section 3.7 Model Group Details

..., model groups can indirectly contain other model groups; the grammar
for content models is therefore recursive.

I believe XML Schema wants to maintain that the content model is a regular
grammar [Hopcroft and Ullman, 1979]. But from the book, we know that if we
allow any arbitrary recursion, content models become context-free.

For example, I am not sure if the following group definitions is invalid
<xsd:group name="X">
    <xsd:sequence minOccurs=0, maxOccurs=1>
        <xsd:element ref="A"/>
        <xsd:group ref="Y"/>
        <xsd:element ref="B"/>
    </xsd:sequence>
</xsd:group>

<xsd:group name="Y">
   <xsd:group ref="X"/>
</xsd:group>

The above content model defines X = A^n B^n, which is context-free.

I believe this was overloooked by Schema WG?

I would like to mention how other schemas or equivalent overcome this.
XDuce from Upenn, allows only right linear production rules which is a
normalized representation of a regular grammar [HU79].
RELAX does not allow any recursion and this ensures that the content model
is string regular.

I would be glad to know whether these observations are valid in the
context of XML Schema.

- Murali.
Received on Thursday, 12 October 2000 12:13:48 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Sunday, 6 December 2009 18:12:48 GMT