<p>One not considered in your list is <a href="http://portal.acm.org/citation.cfm?id=321249">Derivatives of Regular Expressions</a> by Janusz Brzozowski, Journal of the ACM 1964, which was recently reconsidered by Scott Owens, John Reppy, and Aaron Turon in <a href="http://www.cl.cam.ac.uk/~so294/documents/jfp09.pdf">Regular-expression derivatives re-examined. Journal of Functional Programming (2009), 19: 173-190</a>, who provide a practical implementation of the technique for an extended notation for regular expressions.</p>

CC BY-SA 2.5
2010-11-19T09:44:05.537Z
Antimirov is a non-deterministic variant of Brzozowski.
Sylvain
CC BY-SA 2.5
2010-11-19T09:45:29.627Z
The name certainly sounded familiar.
Dave Clarke
CC BY-SA 2.5
2010-11-19T11:03:34.900Z
thanks for the 're-examined' article, I had not seen that!
s8soj3o289
CC BY-SA 2.5
2010-11-19T09:13:33.457Z
2010-11-19T09:13:33.457Z
Dave Clarke
<p>Watson (Tech. Rep. Univ. Eindhoven 1995) has written a taxonomy of finite automata construction algorithms; a few more recent developments are found below. </p>

<p>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&amp;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 &amp; Ziadi (Discr. Appl. Math 2004) and by Gulan (Tech. Rep. Univ. Trier, 2010).</p>

<p>Regarding epsilon-free NFAs, I want to mention the earlier work by Berry &amp; Sethi (TCS 1986) and by Brüggemann-Klein (TCS 1993), but that is probably covered by Watson's taxonomy. </p>

<p>Hagenah and Muscholl (RAIRO 2000) give a fast parallel version of Hromkovic, Seibert &amp; 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.</p>

<p>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).</p>

CC BY-SA 2.5
2010-11-24T22:21:54.747Z
this is a great answer, thank you very much.  i see you've also recently published a book on the subject - might i also ask whether a. it is available on-line in any form, and b. does it, or have you ever looked at 'average case' complexity for specific domains?  im primarily interested in applications to nlp where some as yet largely anecdotal evidence suggests that average case complexity of some of these algorithms differs significantly from the worst case scenarios described in the cs literature.
s8soj3o289
CC BY-SA 2.5
2010-11-24T22:23:18.800Z
also im not quite sure what etiquette dictates in terms of selecting an answer.  your answer is clearly superior to the one i selected previously.
s8soj3o289
CC BY-SA 2.5
2010-11-24T22:38:19.827Z
Only the teaser of the book is available online for free.
Hermann Gruber
CC BY-SA 2.5
2010-11-24T22:41:43.100Z
Regarding average case state complexity, there is also the paper on average NFA size for finite languages with M. Holzer (TCS 2007); but most related seems to be the work by Nicaud on Glushkov automata (LATA 2009); there is also a forthcoming paper by Nicaud, Pivoteau & Razet (FSTTCS 2010) with an interesting title - I wasn't able to take a look yet.
Hermann Gruber
CC BY-SA 2.5
2010-11-26T08:27:12.630Z
Gouveia, Moreira & Reis (CiE 2010) run experiments on RE to NFA conversion. Broda, Machiavelo, Moreira & Reis (DLT 2010) compare the number of states of position (Glushkov) automata and of equation (Antimirov) automata on the average. This might be also of interest.
Hermann Gruber
CC BY-SA 2.5
2010-11-24T22:04:30.823Z
2010-11-24T22:04:30.823Z
Hermann Gruber
<p>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.</p>

<p>I'm aware of several of the 'bigger' names, e.g.,</p>

<hr>

<p><strong>Thompson</strong></p>

<p>"Regular Expression Search Algorithm", Thompson, 1968</p>

<p><strong>Glushkov</strong></p>

<p>"A New Quadratic Algorithm to Convert a Regular Expression into an Automaton", Ponty, et. al, 1996</p>

<p><strong>Antimirov</strong></p>

<p>"Partial Derivatives of Regular Expressions and Finite Automata Constructions", Antimirov, 1996</p>

<p><strong>Follow</strong></p>

<p>"Follow Automata", Ilie, et. al, 2003; </p>

<p>"Computing the follow automaton of an expression", Champarnaud, et. al, 2002</p>

<p><strong>Hromkovic</strong></p>

<p>"Translating Regular Expressions into Small e-Free Nondeterministic Finite Automata", Hromkovic, et. al, 2001</p>

<hr>

<p>and their distinguishing properties (epsilon-free-ness, determinism, size, minimization, etc.) but I know this is not an exhaustive list.</p>

<p>I'm particularly interested in algorithms which present either significantly different time complexities to those listed above, and/or significantly different topologies.</p>

<p>If you know of others, a link to a paper which describes the construction algorithm <strong>in detail</strong> would be greatly appreciated (read necessary if I'm going to implement it!)</p>

<p>Edit: Added some references as per requested.</p>

CC BY-SA 2.5
2010-11-19T10:44:25.177Z
@Radu GRIGore I added some references.  These are the best references that I know of for these automata, but there may be others.
s8soj3o289
CC BY-SA 2.5
2010-11-19T13:36:33.550Z
For Glushkov my usual reference is J. Berstel and J.-E. Pin, "Local languages and the Berry–Sethi algorithm", 1996.
Sylvain
CC BY-SA 2.5
2010-11-19T14:14:49.643Z
By the way, you may find implementations of some of those algorithms in the Vaucanson C++ library, for reference on constructing these algorithms. https://trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms/ (in which standard_of = Glushkov, thompson_of = Thompson, derived_term_automaton = Antimirov, brzozowski = Brzozowski)
Michaël Cadilhac
CC BY-SA 2.5
2010-11-20T04:42:51.160Z
@michael-cadilhac Thanks for the pointer.  Wish I'd known about this before I implemented the others myself!  I'll definitely take a look.
s8soj3o289
<automata-theory><fl.formal-languages><regular-expressions>
Taxonomy of notable regular expression automata
s8soj3o289
# Taxonomy of notable regular expression automata

(Asked by: username_0 on 2010-11-19)

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.,

---

**Thompson**

"Regular Expression Search Algorithm", Thompson, 1968

**Glushkov**

"A New Quadratic Algorithm to Convert a Regular Expression into an Automaton", Ponty, et. al, 1996

**Antimirov**

"Partial Derivatives of Regular Expressions and Finite Automata Constructions", Antimirov, 1996

**Follow**

"Follow Automata", Ilie, et. al, 2003;

"Computing the follow automaton of an expression", Champarnaud, et. al, 2002

**Hromkovic**

"Translating Regular Expressions into Small e-Free Nondeterministic Finite Automata", Hromkovic, et. al, 2001

---

and 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.

**Tags:** automata-theory, fl.formal-languages, regular-expressions

> **Comments:**
> **username_0**: @Radu GRIGore I added some references.  These are the best references that I know of for these automata, but there may be others.  
> **username_1**: For Glushkov my usual reference is J. Berstel and J.-E. Pin, "Local languages and the Berry–Sethi algorithm", 1996.  
> **username_2**: By the way, you may find implementations of some of those algorithms in the Vaucanson C++ library, for reference on constructing these algorithms. https://trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms/ (in which standard_of = Glushkov, thompson_of = Thompson, derived_term_automaton = Antimirov, brzozowski = Brzozowski)  
> **username_0**: @michael-cadilhac Thanks for the pointer.  Wish I'd known about this before I implemented the others myself!  I'll definitely take a look.  

---

## 2 answers

### Answer by username_4 on 2010-11-24. Score: 7 | Accepted answer

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 Brüggemann-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).

> **Comments:**
> **username_0**: this is a great answer, thank you very much.  i see you've also recently published a book on the subject - might i also ask whether a. it is available on-line in any form, and b. does it, or have you ever looked at 'average case' complexity for specific domains?  im primarily interested in applications to nlp where some as yet largely anecdotal evidence suggests that average case complexity of some of these algorithms differs significantly from the worst case scenarios described in the cs literature.  
> **username_0**: also im not quite sure what etiquette dictates in terms of selecting an answer.  your answer is clearly superior to the one i selected previously.  
> **username_4**: Only the teaser of the book is available online for free.  
> **username_4**: Regarding average case state complexity, there is also the paper on average NFA size for finite languages with M. Holzer (TCS 2007); but most related seems to be the work by Nicaud on Glushkov automata (LATA 2009); there is also a forthcoming paper by Nicaud, Pivoteau & Razet (FSTTCS 2010) with an interesting title - I wasn't able to take a look yet.  
> **username_4**: Gouveia, Moreira & Reis (CiE 2010) run experiments on RE to NFA conversion. Broda, Machiavelo, Moreira & Reis (DLT 2010) compare the number of states of position (Glushkov) automata and of equation (Antimirov) automata on the average. This might be also of interest.  

---

### Answer by username_3 on 2010-11-19. Score: 5

One not considered in your list is [Derivatives of Regular Expressions](http://portal.acm.org/citation.cfm?id=321249) by Janusz Brzozowski, Journal of the ACM 1964, which was recently reconsidered by Scott Owens, John Reppy, and Aaron Turon in [Regular-expression derivatives re-examined. Journal of Functional Programming (2009), 19: 173-190](http://www.cl.cam.ac.uk/~so294/documents/jfp09.pdf), who provide a practical implementation of the technique for an extended notation for regular expressions.

> **Comments:**
> **username_1**: Antimirov is a non-deterministic variant of Brzozowski.  
> **username_3**: The name certainly sounded familiar.  
> **username_0**: thanks for the 're-examined' article, I had not seen that!  

---

