W3C home > Mailing lists > Public > xmlschema-dev@w3.org > October 2012

Re: Order indicators in the .xsd file

From: Pete Cordell <petexmldev@codalogic.com>
Date: Thu, 18 Oct 2012 16:05:25 +0100
Message-ID: <5BC9BE678F6448AF9CCF30442B223832@codalogic>
To: "C. M. Sperberg-McQueen" <cmsmcq@blackmesatech.com>, "Michael Kay" <mike@saxonica.com>
Cc: <xmlschema-dev@w3.org>
Original Message From: "C. M. Sperberg-McQueen"

> - While enumerating 24! or 120! disjuncts in a large regular expression
> or content model whose top-level operator is choice may
> exceed current engineering capacity, it is not beyond the wit of
> human beings or the memory capacity of current machines to
> construct a finite state automaton for the same language; if there
> are 23 child elements, of which 3 have the range {1, unbounded},
> 4 more have the range {1,1} and 16 have the range {0,1}, the
> FSA will need 2 ** 23 states.

Do you not also need your FSM to cater for sequences like:

    ababababa ... abac

etc?  Or does XSD 1.1 require all the 'a's to be together and all the 'b's 
to be together and so on.

The former case looks to require an infinite number of states to me, and the 
latter 23! (25x10^21) states.

> (This is, of course, the same
> state machine an XSD 1.1 machine will need to manage the
> all-group one might write for this content model.)

A better engineering option is to just use 23 counters (possibly even as 
little as 23 bits in fact) and implement it in a similar fashion to Ken's 
suggestion to do a xs:choice and then an xs:assert checking the occurrence 
counts were correct.

Pete Cordell
Codalogic Ltd
Twitter: http://twitter.com/petecordell
Interface XML to C++ the easy way using C++ XML
data binding to convert XSD schemas to C++ classes.
Visit http://codalogic.com/lmx/ or http://www.xml2cpp.com
for more info
Received on Thursday, 18 October 2012 15:05:49 UTC

This archive was generated by hypermail 2.4.0 : Friday, 17 January 2020 23:16:02 UTC