OASIS Mailing List ArchivesView the OASIS mailing list archive below
or browse/search using MarkMail.


Help: OASIS Mailing Lists Help | MarkMail Help

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]
Do you know about Brzozowski derivatives? You should!

Hi Folks,


Recently I learned about something called Brzozowski derivatives [1]. It’s pretty important stuff to us XML folk.


In 2005 Michael Sperberg-McQueen wrote a paper [2] that shows how to use Brzozowski derivatives in implementing an XML Schema validator.


James Clark uses Brzozowski derivatives in his RelaxNG validator, Jing. Brzozowski derivatives help reduce the cost of Relax NG's non-determinism and co-occurrence constraints.


Brzozowski derivatives are used in Sun's MSV validator.


Bob Foster has described (mostly in blog articles) a number of applications of Brzozowski derivatives, including validation of expressions with integer-range exponents on sub-expressions.


Martin Schmidt applies Brzozowski derivatives in his validating XML parser.


The earliest suggestion that Brzozowski derivatives ought to be applied in validation software appears to be due to Joe English. (Joe used to post to this list. Where is Joe?)


One reviewer writes this about Brzozowski’s paper:


This is one of my favorite papers. It describes a very cute algorithm

for building deterministic finite automata directly from a regular

expression. The key trick is the idea of a derivative of a regular

expression with respect to a string, which is a non-obvious but

fun idea.


As I said, I just recently learned about Brzozowski derivatives. I am starting to read MSM’s paper.


I wonder what other important/foundational papers I have missed? Can you recommend other foundational papers?




[1] http://delivery.acm.org/10.1145/330000/321249/p481-brzozowski.pdf?ip=


[2] http://conferences.idealliance.org/extreme/html/2005/SperbergMcQueen01/EML2005SperbergMcQueen01.html#fromid2643582

[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index]

News | XML in Industry | Calendar | XML Registry
Marketplace | Resources | MyXML.org | Sponsors | Privacy Statement

Copyright 1993-2007 XML.org. This site is hosted by OASIS