Taxonomia de autômatos notáveis ​​de expressão regular

Estou tentando elaborar uma taxonomia de algoritmos para transformar expressões regulares em autômatos, a fim de executar alguns testes empíricos de suas propriedades de complexidade em domínios específicos.

Estou ciente de vários nomes 'maiores', por exemplo,

Thompson

"Algoritmo de pesquisa de expressão regular", Thompson, 1968

Glushkov

"Um novo algoritmo quadrático para converter uma expressão regular em um autômato", Ponty, et. al, 1996

Antimirov

"Derivadas parciais de expressões regulares e construções de autômatos finitos", Antimirov, 1996

Segue

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

"Computando o autômato a seguir de uma expressão", Champarnaud, et. al, 2002

Hromkovic

"Traduzindo expressões regulares em pequenos autômatos finitos não determinísticos e-livres", Hromkovic, et. al, 2001

e suas propriedades distintivas (isenção de epsilon, determinismo, tamanho, minimização etc.), mas sei que essa não é uma lista exaustiva.

Estou particularmente interessado em algoritmos que apresentam complexidades de tempo significativamente diferentes daquelas listadas acima e / ou topologias significativamente diferentes.

Se você conhece outras pessoas, um link para um artigo que descreve o algoritmo de construção em detalhes seria muito apreciado (leia-se necessário se eu vou implementá-lo!)

Editar: adicionadas algumas referências conforme solicitado.

Watson (Rep. Técnica Univ. Eindhoven 1995) escreveu uma taxonomia de algoritmos de construção de autômatos finitos; alguns desenvolvimentos mais recentes são encontrados abaixo.

Para NFAs com transições epsilon, o livro da teoria da análise de Sippu / Soisalon-Soininen (Springer, 1998) contém uma variante da construção de Thompson. Ilie e Yu (I&C 2003) e Gulan e Fernau (FSTTCS 2008) fornecem versões refinadas da construção clássica. O tamanho mínimo necessário de epsilon-NFAs correspondentes a expressões regulares é mais estudado por Gruber e Gulan (LATA 2010). A estrutura dos dígrafos subjacentes resultantes da construção de Thompson é estudada por Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) e por Gulan (Rep. Tecn. Univ. Trier, 2010).

Em relação às NFAs sem epsilon, quero mencionar o trabalho anterior de Berry & Sethi (TCS 1986) e Brüggemann-Klein (TCS 1993), mas que provavelmente é coberto pela taxonomia de Watson.

Hagenah e Muscholl (RAIRO 2000) fornecem uma versão paralela rápida do algoritmo de Hromkovic, Seibert & Wilke (HSW). O limite inicial mais baixo do tamanho (número de transições) de NFAs sem epsilon por HSW é aprimorado pelo Lifshits (IPL 2003). Geffert (JCSS 2003) melhora o limite superior no caso de alfabetos binários; Posteriormente, Schnitger (STACS 2006) melhora o limite inferior do tamanho dos NFAs isentos de épsilon (para tamanhos de alfabeto cada vez maiores, o algoritmo do HSW produz NFAs assintoticamente ótimos) e mostra esse tamanho é suficiente para alfabetos binários.$n\cdot 2^{O(\log^*n)}$

Observe também: Em relação aos algoritmos rápidos para correspondência de expressões regulares, conheço o trabalho recente de Bille e Thorup (ICALP 2009, SODA 2010). Eles usam a construção clássica da Thompson (além de, obviamente, muitos truques para obter velocidade).

Um não considerado em sua lista é Derivatives of Regular Expressions, de Janusz Brzozowski, Journal of the ACM 1964, que foi recentemente reconsiderado por Scott Owens, John Reppy e Aaron Turon em derivados de expressão regular reexaminados. Journal of Functional Programming (2009), 19: 173-190 , que fornece uma implementação prática da técnica para uma notação estendida para expressões regulares.