As posted and confirmed on the mailinglist (http://mail.gnome.org/archives/xml/2012-February/msg00058.html), xmllint considers the following schema as not determinist, although it seems to be deterministic (XSV, Xerces and Visual Studio have no problem with it):

  <?xml version="1.0" encoding="UTF-8"?>
  <xs:schema xmlns:xs="http://www.w3.org/2001/XMLSchema">
    <xs:element name="rules">
      <xs:complexType>
        <xs:sequence>
          <xs:element name="rule" minOccurs="0" maxOccurs="unbounded"/>
          <xs:sequence minOccurs="0" maxOccurs="1">
            <xs:element name="specialRule" minOccurs="1" maxOccurs="1"/>
            <xs:element name="rule" minOccurs="0" maxOccurs="unbounded"/>
          </xs:sequence>
        </xs:sequence>
      </xs:complexType>
    </xs:element>
  </xs:schema>

xmllint outputs:

  rules.xsd:4: element complexType: Schemas parser error : local complex type: The content model is not determinist.
  WXS schema rules.xsd failed to compile

The intention is to express that there can be any number of "rule"
elements, and there can be at most one "specialRule" (at any position
in between, before, or after the "rule"s). So the following xml's are
all valid:

  <?xml version="1.0" encoding="UTF-8"?>
  <rules>
    <rule/>
    <rule/>
    <specialRule/>
    <rule/>
  </rules>

  <?xml version="1.0" encoding="UTF-8"?>
  <rules>
    <specialRule/>
  </rules>

  <?xml version="1.0" encoding="UTF-8"?>
  <rules>
    <specialRule/>
    <rule/>
    <rule/>
    <rule/>
  </rules>

  <?xml version="1.0" encoding="UTF-8"?>
  <rules>
    <rule/>
    <rule/>
    <rule/>
  </rules>

But this one isn't (two specialRules):

  <?xml version="1.0" encoding="UTF-8"?>
  <rules>
    <specialRule/>
    <rule/>
    <rule/>
    <specialRule/>
    <rule/>
  </rules>