A delay insensitive regular expression recognizer

Abstract: "Several types of synchronous Regular Expression (RE) recognizers have been proposed by several authors. This paper describes a self-timed and delay-independent RE recognizer. The problem is non-trivial because of the [epsilon]-closure operation that is implicitly performed every cycle of the recognition process. The design is based on expression-tree recognizers, and has a self-timed cycle time O(h) where h is the high of the parse tree of the RE. Since it is an expression-tree recognizer it has a compact O(N) layout algorithm, where N is the size of the RE. The design also results in an synchronous RE recognizer with the shortest worst case cycle time O(h) reported for recognizers with area O(N).