[XML-DEV Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: New release (2.8) of XSV

• To: Jeff Rafter <lists@j...>
• Subject: Re: New release (2.8) of XSV
• From: ht@i... (Henry S. Thompson)
• Date: Fri, 08 Oct 2004 17:30:50 +0100
• Cc: xmlschema-dev@w..., xml-dev@l...
• In-reply-to: <4166BCB7.6020309@j...> (Jeff Rafter's message of"Fri, 08 Oct 2004 09:13:43 -0700")
• References: <f5bfz4pvc2n.fsf@e...><4166BCB7.6020309@j...>
• User-agent: Gnus/5.1006 (Gnus v5.10.6) XEmacs/21.4 (Security ThroughObscurity, linux)

Jeff Rafter <lists@j...> writes:

> Does this mean that you have modified the approach set forth in
> http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html? 

Yes.  That approach unfolds numeric exponents, producing a number of
states which grows linearly with maxOccurs for elements and
non-nesting groups, and grows exponentially for nesting groups, that
is if you have (a, b{2,5}, c){1,100} the number of states is
Order(500).

The new approach is linear in the number of particles, because it uses
counters, not unfolding.

> If so, do you have any metrics on changes to the time complexity?

Should not change the _runtime_ complexity at all, which was always
the normal FSM complexity.  Changes the _compile-time_ complexity
significantly, from exponential to linear.

The really good news is that this approach doesn't require XSV to punt
in the face of large exponents, which it used to do (i.e. treated all
numbers > 100 in min/maxOccurs as if they _were_ 100).  All other
existing processors do something similar (that is, punt above some
number), I believe.

I hope to write up the new algorithm RSN . . .

ht
-- 
 Henry S. Thompson, HCRC Language Technology Group, University of Edinburgh
                     Half-time member of W3C Team
    2 Buccleuch Place, Edinburgh EH8 9LW, SCOTLAND -- (44) 131 650-4440
            Fax: (44) 131 650-4587, e-mail: ht@i...
                   URL: http://www.ltg.ed.ac.uk/~ht/
[mail really from me _always_ has this .sig -- mail without it is forged spam]

• Follow-Ups:
  • Re: New release (2.8) of XSV
    • From: Burak Emir <Burak.Emir@e...>
  • Re: New release (2.8) of XSV
    • From: Bob Foster <bob@o...>

• References:
  • New release (2.8) of XSV
    • From: ht@i... (Henry S. Thompson)
  • Re: New release (2.8) of XSV
    • From: Jeff Rafter <lists@j...>

• Prev by Date: Re: New release (2.8) of XSV
• Next by Date: Re: New release (2.8) of XSV
• Previous by thread: Re: New release (2.8) of XSV
• Next by thread: Re: New release (2.8) of XSV
• Index(es):
  • Date
  • Thread