Nice explanation. One more thing: this also leads to an algorithm for doing ordinary, non-incremental regular expression matching in O(lg n) time on a parallel machine. It uses a clever method which I think was first discovered on the old Connection Machines by Danny Hillis and Guy Steele:

http://cva.stanford.edu/classes/cs99s/papers/hillis-steele-d...