I'm trying to draw up a taxonomy of algorithms for transforming regular expressions into automata so as to perform some empirical tests of their complexity properties in specific domains.I'm aware of several of the 'bigger' names, e.g.,ThompsonRegular Expression Search Algorithm, Thompson, 1968GlushkovA New Quadratic Algorithm to Convert a Regular Expression into an Automaton, Ponty, et. al, 1996AntimirovPartial Derivatives of Regular Expressions and Finite Automata Constructions, Antimirov, 1996FollowFollow Automata, Ilie, et. al, 2003; Computing the follow automaton of an expression, Champarnaud, et. al, 2002HromkovicTranslating Regular Expressions into Small e-Free Nondeterministic Finite Automata, Hromkovic, et. al, 2001and their distinguishing properties (epsilon-free-ness, determinism, size, minimization, etc.) but I know this is not an exhaustive list.I'm particularly interested in algorithms which present either significantly different time complexities to those listed above, and/or significantly different topologies.If you know of others, a link to a paper which describes the construction algorithm in detail would be greatly appreciated (read necessary if I'm going to implement it!)Edit: Added some references as per requested.
Taxonomy of notable regular expression automata
automata theory;fl.formal languages;regular expressions
Watson (Tech. Rep. Univ. Eindhoven 1995) has written a taxonomy of finite automata construction algorithms; a few more recent developments are found below. For NFAs with epsilon-transitions, the parsing theory book by Sippu/Soisalon-Soininen (Springer, 1998) contains a variant of Thompson's construction. Ilie and Yu (I&C 2003) and Gulan and Fernau (FSTTCS 2008) give refined versions of the classical construction. The minimum required size of epsilon-NFAs corresponding to regular expressions is further studied by Gruber and Gulan (LATA 2010). The structure of the underlying digraphs resulting from Thompson's construction is studied by Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) and by Gulan (Tech. Rep. Univ. Trier, 2010).Regarding epsilon-free NFAs, I want to mention the earlier work by Berry & Sethi (TCS 1986) and by Brggemann-Klein (TCS 1993), but that is probably covered by Watson's taxonomy. Hagenah and Muscholl (RAIRO 2000) give a fast parallel version of Hromkovic, Seibert & Wilke's (HSW) algorithm. The initial lower bound on size (number of transitions) of epsilon-free NFAs by HSW is improved by Lifshits (IPL 2003). Geffert (JCSS 2003) improves the upper bound in the case of binary alphabets; Later Schnitger (STACS 2006) improves the lower bound on the size of epsilon-free NFAs (for largely growing alphabet sizes, the algorithm by HSW produces asymptotically optimal NFAs), and shows that size $n\cdot 2^{O(\log^*n)}$ suffices for binary alphabets.Also note: Regarding fast algorithms for regular expression matching, I am aware of recent work by Bille and Thorup (ICALP 2009, SODA 2010). They use the classical Thompson construction (plus of course many tricks for getting speed).