11
$\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.

Improve this question
$\endgroup$
4
  • $\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, 2010 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, 2010 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, 2010 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, 2010 at 4:42

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
5
  • 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, 2010 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, 2010 at 22:23
  • $\begingroup$ Only the teaser of the book is available online for free. $\endgroup$
    – Hermann Gruber
    Nov 24, 2010 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, 2010 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, 2010 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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