Taxonomía de autómatas notables de expresión regular

10

Estoy tratando de elaborar una taxonomía de algoritmos para transformar expresiones regulares en autómatas para realizar algunas pruebas empíricas de sus propiedades de complejidad en dominios específicos.

Soy consciente de varios de los nombres 'más grandes', por ejemplo,

Thompson

"Algoritmo de búsqueda de expresiones regulares", Thompson, 1968

Glushkov

"Un nuevo algoritmo cuadrático para convertir una expresión regular en un autómata", Ponty, et. al, 1996

Antimirov

"Derivados parciales de expresiones regulares y construcciones de autómatas finitos", Antimirov, 1996

Seguir

"Seguir autómatas", Ilie, et. al, 2003;

"Calcular el autómata de una expresión", Champarnaud, et. al, 2002

Hromkovic

"Traducción de expresiones regulares en pequeños autómatas finitos no deterministas e-libres", Hromkovic, et. al, 2001

y sus propiedades distintivas (sin épsilon, determinismo, tamaño, minimización, etc.) pero sé que esta no es una lista exhaustiva.

Estoy particularmente interesado en algoritmos que presentan complejidades de tiempo significativamente diferentes a las enumeradas anteriormente y / o topologías significativamente diferentes.

Si conoce a otros, un enlace a un documento que describe el algoritmo de construcción en detalle sería muy apreciado (¡lea necesario si voy a implementarlo!)

Editar: se agregaron algunas referencias según lo solicitado.

automata-theory fl.formal-languages regular-expressions s8soj3o289
fuente
@Radu GRIGore Agregué algunas referencias. Estas son las mejores referencias que conozco para estos autómatas, pero puede haber otras.
s8soj3o289
1
Para Glushkov, mi referencia habitual es J. Berstel y J.-E. Pin, "Idiomas locales y el algoritmo Berry-Sethi", 1996.
Sylvain
1
Por cierto, puede encontrar implementaciones de algunos de esos algoritmos en la biblioteca Vaucanson C ++, como referencia para construir estos algoritmos. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (en el que standard_of = Glushkov, thompson_of = Thompson, deriva_term_automaton = Antimirov, brzozowski = Brzozowski)
Michaël Cadilhac
@ michael-cadilhac Gracias por el puntero. ¡Ojalá hubiera sabido esto antes de implementar los otros yo mismo! Definitivamente voy a echar un vistazo.
s8soj3o289

Respuestas:

7

Watson (Tech. Rep. Univ. Eindhoven 1995) ha escrito una taxonomía de algoritmos de construcción de autómatas finitos; Algunas novedades más recientes se encuentran a continuación.

Para los NFA con transiciones épsilon, el libro de teoría de análisis de Sippu / Soisalon-Soininen (Springer, 1998) contiene una variante de la construcción de Thompson. Ilie y Yu (I&C 2003) y Gulan y Fernau (FSTTCS 2008) dan versiones refinadas de la construcción clásica. Gruber y Gulan (LATA 2010) estudian más a fondo el tamaño mínimo requerido de epsilon-NFA correspondientes a expresiones regulares. La estructura de los dígrafos subyacentes resultantes de la construcción de Thompson es estudiada por Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) y por Gulan (Tech. Rep. Univ. Trier, 2010).

Con respecto a los NFA sin épsilon, quiero mencionar el trabajo anterior de Berry & Sethi (TCS 1986) y de Brüggemann-Klein (TCS 1993), pero eso probablemente esté cubierto por la taxonomía de Watson.

n⋅2O(log∗⁡n)

También tenga en cuenta: con respecto a los algoritmos rápidos para la coincidencia de expresiones regulares, conozco el trabajo reciente de Bille y Thorup (ICALP 2009, SODA 2010). Utilizan la construcción clásica de Thompson (además, por supuesto, muchos trucos para obtener velocidad).

Hermann Gruber
fuente
1
Esta es una gran respuesta, muchas gracias. Veo que también ha publicado recientemente un libro sobre el tema, ¿podría preguntar si a. está disponible en línea en cualquier forma, y ​​b. ¿lo ha hecho, o alguna vez has mirado la complejidad del "caso promedio" para dominios específicos? Estoy principalmente interesado en las aplicaciones para PNL donde algunas evidencias aún bastante anecdóticas sugieren que la complejidad del caso promedio de algunos de estos algoritmos difiere significativamente de los peores escenarios descritos en la literatura cs.
s8soj3o289
Tampoco estoy muy seguro de qué etiqueta dicta en términos de selección de una respuesta. Su respuesta es claramente superior a la que seleccioné anteriormente.
s8soj3o289
Solo el avance del libro está disponible en línea de forma gratuita.
Hermann Gruber
Con respecto a la complejidad promedio del estado del caso, también está el documento sobre el tamaño promedio de NFA para idiomas finitos con M. Holzer (TCS 2007); pero lo más relacionado parece ser el trabajo de Nicaud sobre los autómatas Glushkov (LATA 2009); También hay un próximo documento de Nicaud, Pivoteau & Razet (FSTTCS 2010) con un título interesante: aún no he podido echarle un vistazo.
Hermann Gruber
Gouveia, Moreira y Reis (CiE 2010) realizan experimentos en la conversión de RE a NFA. Broda, Machiavelo, Moreira y Reis (DLT 2010) comparan el número de autómatas de estado de posición (Glushkov) y de autómata de ecuación (Antimirov) en promedio. Esto también podría ser de interés.
Hermann Gruber el
5

Uno no considerado en su lista es Derivados de expresiones regulares de Janusz Brzozowski, Journal of the ACM 1964, que recientemente fue reconsiderado por Scott Owens, John Reppy y Aaron Turon en Derivados de expresiones regulares reexaminados. Journal of Functional Programming (2009), 19: 173-190 , que proporcionan una implementación práctica de la técnica para una notación extendida para expresiones regulares.

Dave Clarke
fuente
2
Antimirov es una variante no determinista de Brzozowski.
Sylvain
El nombre ciertamente sonaba familiar.
Dave Clarke
gracias por el artículo 'reexaminado', ¡no lo había visto!
s8soj3o289