Recognizing Regular Expressions by means of Dataflows Networks

Abstract:
This paper addresses the problem of building a Boolean dataflow network (sequential circuit) recognizing the language described by a regular expression. The main result is that both the construction time and the size of the resulting network are linear with respect to the size of the regular expression.

Reference:

@INPROCEEDINGS{reglo:icalp96,
AUTHOR = {P. Raymond},
TITLE = {Recognizing Regular Expressions by means of Dataflows
Networks},
BOOKTITLE =  {23rd International Colloquium on Automata, Languages,
and Programming, (ICALP'96)},
ADDRESS = {Paderborn, Germany},
MONTH = jul,
PUBLISHER = {LNCS 1099, Springer Verlag},
YEAR = 1996
}

Postscript file