10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @Radu GRIGore I added some references. These are the best references that I know of for these automata, but there may be others. $\endgroup$ – s8soj3o289 Nov 19 '10 at 10:44
  • 1
    $\begingroup$ For Glushkov my usual reference is J. Berstel and J.-E. Pin, "Local languages and the Berry–Sethi algorithm", 1996. $\endgroup$ – Sylvain Nov 19 '10 at 13:36
  • 1
    $\begingroup$ By the way, you may find implementations of some of those algorithms in the Vaucanson C++ library, for reference on constructing these algorithms. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (in which standard_of = Glushkov, thompson_of = Thompson, derived_term_automaton = Antimirov, brzozowski = Brzozowski) $\endgroup$ – Michaël Cadilhac Nov 19 '10 at 14:14
  • $\begingroup$ @michael-cadilhac Thanks for the pointer. Wish I'd known about this before I implemented the others myself! I'll definitely take a look. $\endgroup$ – s8soj3o289 Nov 20 '10 at 4:42
7
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – s8soj3o289 Nov 24 '10 at 22:21
  • $\begingroup$ 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. $\endgroup$ – s8soj3o289 Nov 24 '10 at 22:23
  • $\begingroup$ Only the teaser of the book is available online for free. $\endgroup$ – Hermann Gruber Nov 24 '10 at 22:38
  • $\begingroup$ 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. $\endgroup$ – Hermann Gruber Nov 24 '10 at 22:41
  • $\begingroup$ 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. $\endgroup$ – Hermann Gruber Nov 26 '10 at 8:27
5
$\begingroup$

One not considered in your list is Derivatives of Regular Expressions 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, who provide a practical implementation of the technique for an extended notation for regular expressions.

$\endgroup$
  • 2
    $\begingroup$ Antimirov is a non-deterministic variant of Brzozowski. $\endgroup$ – Sylvain Nov 19 '10 at 9:44
  • $\begingroup$ The name certainly sounded familiar. $\endgroup$ – Dave Clarke Nov 19 '10 at 9:45
  • $\begingroup$ thanks for the 're-examined' article, I had not seen that! $\endgroup$ – s8soj3o289 Nov 19 '10 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.