Comment about recursive group definition

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 UTC