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?
/Roger
[1] http://delivery.acm.org/10.1145/330000/321249/p481-brzozowski.pdf?ip=129.83.31.1&id=321249&acc=ACTIVE%20SERVICE&key=A9ED11D7A520B19D.4D4702B0C3E38B35.4D4702B0C3E38B35.4D4702B0C3E38B35&CFID=516451352&CFTOKEN=97056767&__acm__=1433269367_45f47796931591ce1bb32a8223044057
[2] http://conferences.idealliance.org/extreme/html/2005/SperbergMcQueen01/EML2005SperbergMcQueen01.html#fromid2643582
Cart
