W3C home > Mailing lists > Public > xmlschema-dev@w3.org > December 2000

Re: What does 'non-deterministic content model for type' mean?

From: Martin J. Duerst <duerst@w3.org>
Date: Mon, 25 Dec 2000 10:37:19 +0900
Message-Id: <4.2.0.58.J.20001225103434.009f1c30@sh.w3.mag.keio.ac.jp>
To: ht@cogsci.ed.ac.uk (Henry S. Thompson), Michael.Burns@sas.com
Cc: xmlschema-dev@w3.org
At 00/12/23 13:57 +0000, Henry S. Thompson wrote:
>Michael Burns <Michael.Burns@sas.com> writes:
>
><snip/>
>
> > FWIW, xsv does eventually properly evaluate the instance and detect
> > the one
> > known irregularity in the content.  (shown below).
> > It just takes it 12 HOURS on my 400Mhz PIII !
>
><snip/>
>
>The reason is that you have a content model of the following form:
>
>  <choice min='0' max='unbounded'>
>   <elt ref='a' max='unbounded'/>
>   <elt ref='b' max='unbounded'/>
>    . . .
>   <elt ref='z' max='unbounded'/>
>  </choice>
>
>Determinising the resulting FSM is exponential in the number of
>elements, and is taking [approximately :-[ forever.
>
>Remove the max='unbounded' from all the refs, the language accepted
>won't change and it runs in about 30 seconds on an old Sun box.

Can we make sure that this example is added as a test case?
If there are implementations that change their execution time
just when something that is implicitly anyway the case is
said explicitly, it's quite surprising.


Regards,   Martin.
Received on Sunday, 24 December 2000 21:09:50 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Tuesday, 11 January 2011 00:14:19 GMT