W3C home > Mailing lists > Public > xmlschema-dev@w3.org > January 2002

Substitution groups and Parsing Efficiency

From: Mark Feblowitz <mfeblowitz@frictionless.com>
Date: Mon, 7 Jan 2002 18:18:16 -0500
Message-ID: <4DBDB4044ABED31183C000508BA0E97F024D5694@fcpostal.frictionless.com>
To: "Xmlschema-Dev (E-mail)" <xmlschema-dev@w3.org>
While (ab)using a particular substitution group, I noticed in the XSV error
report that the fsm for the substitution group was huge.

The substitution group is indeed large (many possible substitutions), and is
referenced in many places, with a cardinality of 0..unbounded. This means
that any number of the substitutions could appear any number of times, and
in any order. This, indeed, would lead to a large fsm - in fact to an "nfsm"
(with a non-finite set of potential states).

My question is, do schema validators typically have efficient algorithms for
handling such cases? How about cases that are finite but large?



Mark Feblowitz                                   [t] 617.715.7231
Frictionless Commerce Incorporated     [f] 617.495.0188 
XML Architect                                     [e]
400 Technology Square, 9th Floor 
Cambridge, MA 02139 
Received on Monday, 7 January 2002 18:18:54 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 14:55:54 UTC