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

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

From: Henry S. Thompson <ht@cogsci.ed.ac.uk>
Date: 23 Dec 2000 13:57:09 +0000
To: Michael.Burns@sas.com
Cc: xmlschema-dev@w3.org
Message-ID: <f5bbsu3qlze.fsf@cogsci.ed.ac.uk>
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.

We'll see if we can detect this case automatically, but in the mean
time be careful . . .

ht
-- 
  Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
          W3C Fellow 1999--2001, part-time member of W3C Team
     2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
	    Fax: (44) 131 650-4587, e-mail: ht@cogsci.ed.ac.uk
		     URL: http://www.ltg.ed.ac.uk/~ht/
Received on Saturday, 23 December 2000 08:57:18 GMT

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