Applications of Brzozowski derivatives to XML Schema processing.
C. Michael Sperberg-McQueen · 2005
Given a regular language L, the Brzozowski derivative of L with respect to some string s is a regular expression which defines what strings can follow s in strings appearing in L. The calculation of Brzozowski derivatives is a convenient and beautiful tool for the algebraic manipulation of content models. It can provide convenient solutions to several problems arising in developing, manipulating, and validating content models in W3C XML Schema: validation, checking the unique-particle-attribution constraint, and testing whether the language accepted by one content model is a subset of that accepted by another. Applications of Brzozowski derivatives to XML Schema processing