Reading paper in computer science is itself an important skill, one you should master. I've detailed some of my problems before in my series on A Play On Regular Expressions, and now that I have a little free time on my hand I'm going to dive into some of the issues that I want to cover in the future.

My Regular Expressions series talked mostly about two different papers: Fischer, Huch and Wilke's A Play on Regular Expressions, and Matt Might's Parsing with Derivatives. One isn't about Brzozowski's derivatives at all; it's about identifying a common mathematical principle by which the boolean yes/no Finite State Automata of the classic Kleene Algebra can be tranformed into a Finite State Transducer by abstracting "up one level" what the automata does. The second describes a long-neglected algorithm for solving the Kleene Algebra that promises some interesting characteristics. My contribution was to show that these papers are compatible— that Might's combinators are actually semirings in disguise— and that Brzozowski's algorithm can be expressed in a systems language with strict memory requirements.

But that's not where the story starts. The story starts with two other papers, one of which I'll be reviewing today. The first paper is Joshua Goodman's 1999 paper, "Semiring Parsing," which I'll be addressing later.

Today's paper is

Regular Expression Derivatives Re-Examined

... by Scott Owens, John Reppy, and Aaron Turon.

Continue Reading