Taxonomie des automates d'expression régulière notables

J'essaie de dresser une taxonomie d'algorithmes pour transformer des expressions régulières en automates afin d'effectuer des tests empiriques de leurs propriétés de complexité dans des domaines spécifiques.

Je connais plusieurs des plus grands noms, par exemple,

Thompson

"Algorithme de recherche d'expression régulière", Thompson, 1968

Glushkov

"Un nouvel algorithme quadratique pour convertir une expression régulière en automate", Ponty, et. al, 1996

Antimirov

"Dérivés partiels d'expressions régulières et de constructions d'automates finis", Antimirov, 1996

Suivre

"Suivez les automates", Ilie, et. al, 2003;

"Calculer l'automate de suivi d'une expression", Champarnaud, et. al, 2002

Hromkovic

"Traduction d'expressions régulières en petits automates finis non déterministes non électroniques", Hromkovic, et. al, 2001

et leurs propriétés distinctives (absence d'epsilon, déterminisme, taille, minimisation, etc.) mais je sais que cette liste n'est pas exhaustive.

Je suis particulièrement intéressé par les algorithmes qui présentent soit des complexités temporelles significativement différentes de celles listées ci-dessus, et / ou des topologies sensiblement différentes.

Si vous en connaissez d'autres, un lien vers un article qui décrit l'algorithme de construction en détail serait grandement apprécié (lire nécessaire si je veux l'implémenter!)

Modifier: Ajout de quelques références selon la demande.

Watson (Tech. Rep. Univ. Eindhoven 1995) a écrit une taxonomie d'algorithmes de construction d'automates finis; quelques développements plus récents se trouvent ci-dessous.

Pour les NFA avec des transitions epsilon, le livre sur la théorie de l'analyse de Sippu / Soisalon-Soininen (Springer, 1998) contient une variante de la construction de Thompson. Ilie et Yu (I&C 2003) et Gulan et Fernau (FSTTCS 2008) donnent des versions raffinées de la construction classique. La taille minimale requise des epsilon-NFA correspondant aux expressions régulières est étudiée plus en détail par Gruber et Gulan (LATA 2010). La structure des digraphes sous-jacents résultant de la construction de Thompson est étudiée par Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) et par Gulan (Tech. Rep. Univ. Trier, 2010).

Concernant les NFA sans epsilon, je veux mentionner les travaux antérieurs de Berry & Sethi (TCS 1986) et de Brüggemann-Klein (TCS 1993), mais qui sont probablement couverts par la taxonomie de Watson.

$n\cdot 2^{O(\log^*n)}$

A noter également: Concernant les algorithmes rapides de mise en correspondance des expressions régulières, je connais les travaux récents de Bille et Thorup (ICALP 2009, SODA 2010). Ils utilisent la construction classique de Thompson (plus bien sûr de nombreuses astuces pour gagner en vitesse).

L'un des éléments non pris en compte dans votre liste est Derivatives of Regular Expressions de Janusz Brzozowski, Journal of the ACM 1964, qui a récemment été reconsidéré par Scott Owens, John Reppy et Aaron Turon dans les dérivés d'expression régulière réexaminés. Journal of Functional Programming (2009), 19: 173-190 , qui fournit une mise en œuvre pratique de la technique d'une notation étendue pour les expressions régulières.