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

10

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.

s8soj3o289
fonte
@Radu GRIGore Adicionei algumas referências. Essas são as melhores referências que eu conheço para esses autômatos, mas pode haver outras.
s8soj3o289
11
Para Glushkov, minha referência usual é J. Berstel e J.-E. Pin, "Idiomas locais e o algoritmo Berry-Sethi", 1996.
Sylvain
11
A propósito, você pode encontrar implementações de alguns desses algoritmos na biblioteca Vaucanson C ++, para referência na construção desses algoritmos. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (em que standard_of = Glushkov, thompson_of = Thompson, derivado_term_automaton = Antimirov, brzozowski = Brzozowski)
Michaël Cadilhac -
@ michael-cadilhac Obrigado pelo ponteiro. Gostaria de saber sobre isso antes de implementar os outros eu mesmo! Definitivamente vou dar uma olhada.
s8soj3o289

Respostas:

7

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.n2O(logn)

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

Hermann Gruber
fonte
11
Esta é uma ótima resposta, muito obrigado. Vejo que você também publicou recentemente um livro sobre o assunto - posso também perguntar se a. está disponível on-line de qualquer forma e b. ou você já analisou a complexidade do 'caso médio' para domínios específicos? estou interessado principalmente em aplicativos para a PNL, onde algumas evidências até agora amplamente sugeridas sugerem que a complexidade média dos casos de alguns desses algoritmos difere significativamente dos piores cenários descritos na literatura cs.
s8soj3o289
também não tenho muita certeza do que a etiqueta determina em termos de seleção de uma resposta. sua resposta é claramente superior à que eu selecionei anteriormente.
s8soj3o289
Apenas o teaser do livro está disponível online gratuitamente.
Hermann Gruber
Em relação à complexidade média do estado de caso, há também o artigo sobre o tamanho médio da NFA para linguagens finitas com M. Holzer (TCS 2007); mas a maioria relacionada parece ser o trabalho de Nicaud no autômato de Glushkov (LATA 2009); também há um artigo de Nicaud, Pivoteau & Razet (FSTTCS 2010) com um título interessante - ainda não pude dar uma olhada.
Hermann Gruber
Gouveia, Moreira & Reis (CiE 2010) realizam experimentos de conversão de RE para NFA. Broda, Machiavelo, Moreira & Reis (DLT 2010) comparam o número de autômatos de estados de posição (Glushkov) e de autômatos de equação (Antimirov) em média. Isso também pode ser interessante.
Hermann Gruber
5

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.

Dave Clarke
fonte
2
Antimirov é uma variante não determinística de Brzozowski.
Sylvain
O nome certamente parecia familiar.
perfil completo de Dave Clarke
obrigado pelo artigo 're-examinado', eu não tinha visto isso!
s8soj3o289