Taxonomie bemerkenswerter Automaten mit regulären Ausdrücken

10

Ich versuche, eine Taxonomie von Algorithmen zur Umwandlung regulärer Ausdrücke in Automaten zu erstellen, um einige empirische Tests ihrer Komplexitätseigenschaften in bestimmten Bereichen durchzuführen.

Mir sind einige der "größeren" Namen bekannt, z.


Thompson

"Regular Expression Search Algorithm", Thompson, 1968

Glushkov

"Ein neuer quadratischer Algorithmus zur Umwandlung eines regulären Ausdrucks in einen Automaten", Ponty et al. al, 1996

Antimirov

"Partielle Ableitungen regulärer Ausdrücke und endlicher Automatenkonstruktionen", Antimirov, 1996

Folgen

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

"Berechnung des folgenden Automaten eines Ausdrucks", Champarnaud, et. al, 2002

Hromkovic

"Übersetzung regulärer Ausdrücke in kleine e-freie nichtdeterministische endliche Automaten", Hromkovic, et. al, 2001


und ihre unterscheidenden Eigenschaften (Epsilon-Freiheit, Determinismus, Größe, Minimierung usw.), aber ich weiß, dass dies keine vollständige Liste ist.

Ich interessiere mich besonders für Algorithmen, die entweder signifikant andere Zeitkomplexitäten als die oben aufgeführten aufweisen und / oder signifikant unterschiedliche Topologien aufweisen.

Wenn Sie andere kennen, wäre ein Link zu einem Artikel, der den Konstruktionsalgorithmus im Detail beschreibt , sehr willkommen (lesen Sie unbedingt, wenn ich ihn implementieren möchte!).

Bearbeiten: Einige Referenzen wie gewünscht hinzugefügt.

s8soj3o289
quelle
@ Radu GRIGore Ich habe einige Referenzen hinzugefügt. Dies sind die besten Referenzen, die ich für diese Automaten kenne, aber es kann auch andere geben.
s8soj3o289
1
Für Glushkov ist meine übliche Referenz J. Berstel und J.-E. Pin, "Lokale Sprachen und der Berry-Sethi-Algorithmus", 1996.
Sylvain
1
Übrigens finden Sie möglicherweise Implementierungen einiger dieser Algorithmen in der Vaucanson C ++ - Bibliothek als Referenz für die Erstellung dieser Algorithmen. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (in dem standard_of = Glushkov, thompson_of = Thompson, derivative_term_automaton = Antimirov, brzozowski = Brzozowski)
Michaël Cadilhac
@ Michael-Cadilhac Danke für den Zeiger. Ich wünschte, ich hätte davon gewusst, bevor ich die anderen selbst implementiert hätte! Ich werde auf jeden Fall einen Blick darauf werfen.
s8soj3o289

Antworten:

7

Watson (Tech. Rep. Univ. Eindhoven 1995) hat eine Taxonomie endlicher Automatenkonstruktionsalgorithmen geschrieben; Einige neuere Entwicklungen sind unten aufgeführt.

Für NFAs mit Epsilon-Übergängen enthält das Parsing-Theoriebuch von Sippu / Soisalon-Soininen (Springer, 1998) eine Variante von Thompsons Konstruktion. Ilie und Yu (I & C 2003) sowie Gulan und Fernau (FSTTCS 2008) geben raffinierte Versionen der klassischen Konstruktion. Die erforderliche Mindestgröße von Epsilon-NFAs, die regulären Ausdrücken entspricht, wird von Gruber und Gulan weiter untersucht (LATA 2010). Die Struktur der zugrunde liegenden Digraphen, die sich aus Thompsons Konstruktion ergeben, wird von Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) und Gulan (Tech. Rep. Univ. Trier, 2010) untersucht.

In Bezug auf epsilonfreie NFAs möchte ich die früheren Arbeiten von Berry & Sethi (TCS 1986) und Brüggemann-Klein (TCS 1993) erwähnen, die jedoch wahrscheinlich von Watsons Taxonomie abgedeckt werden.

Hagenah und Muscholl (RAIRO 2000) geben eine schnelle parallele Version des Algorithmus von Hromkovic, Seibert & Wilke (HSW). Die anfängliche Untergrenze der Größe (Anzahl der Übergänge) von epsilonfreien NFAs durch HSW wird durch Lifshits verbessert (IPL 2003). Geffert (JCSS 2003) verbessert die Obergrenze bei binären Alphabeten; Später verbessert Schnitger (STACS 2006) die Untergrenze der Größe von epsilonfreien NFAs (für weitgehend wachsende Alphabetgrößen erzeugt der Algorithmus von HSW asymptotisch optimale NFAs) und zeigt, dass die Größe reicht für binäre Alphabete aus.n2O(logn)

Beachten Sie auch: In Bezug auf schnelle Algorithmen für den Abgleich regulärer Ausdrücke sind mir die jüngsten Arbeiten von Bille und Thorup bekannt (ICALP 2009, SODA 2010). Sie verwenden die klassische Thompson-Konstruktion (plus natürlich viele Tricks, um Geschwindigkeit zu erreichen).

Hermann Gruber
quelle
1
Dies ist eine großartige Antwort. Vielen Dank. Ich sehe, dass Sie kürzlich auch ein Buch zu diesem Thema veröffentlicht haben - darf ich auch fragen, ob a. es ist in jeder Form online verfügbar und b. Ist dies der Fall, oder haben Sie sich jemals mit der Komplexität des Durchschnittsfalls für bestimmte Domänen befasst? Ich bin hauptsächlich an Anwendungen auf nlp interessiert, bei denen einige noch weitgehend anekdotische Hinweise darauf hindeuten, dass sich die durchschnittliche Fallkomplexität einiger dieser Algorithmen erheblich von den in der cs-Literatur beschriebenen Worst-Case-Szenarien unterscheidet.
s8soj3o289
Ich bin mir auch nicht ganz sicher, was die Etikette bei der Auswahl einer Antwort vorschreibt. Ihre Antwort ist der zuvor ausgewählten eindeutig überlegen.
s8soj3o289
Nur der Teaser des Buches ist kostenlos online verfügbar.
Hermann Gruber
In Bezug auf die durchschnittliche Komplexität des Fallzustands gibt es auch das Papier über die durchschnittliche NFA-Größe für endliche Sprachen mit M. Holzer (TCS 2007); Am verwandtesten scheint jedoch die Arbeit von Nicaud über Glushkov-Automaten zu sein (LATA 2009); Es gibt auch eine bevorstehende Veröffentlichung von Nicaud, Pivoteau & Razet (FSTTCS 2010) mit einem interessanten Titel - ich konnte noch keinen Blick darauf werfen.
Hermann Gruber
Gouveia, Moreira & Reis (CiE 2010) führen Experimente zur Umwandlung von RE in NFA durch. Broda, Machiavelo, Moreira & Reis (DLT 2010) vergleichen die Anzahl der Zustände von Positionsautomaten (Glushkov) und Gleichungsautomaten (Antimirov) im Durchschnitt. Dies könnte auch von Interesse sein.
Hermann Gruber
5

Eines, das in Ihrer Liste nicht berücksichtigt wird, sind Derivate regulärer Ausdrücke von Janusz Brzozowski, Journal of the ACM 1964, das kürzlich von Scott Owens, John Reppy und Aaron Turon in Derivaten regulärer Ausdrücke erneut untersucht wurde. Journal of Functional Programming (2009), 19: 173-190 , die eine praktische Implementierung der Technik für eine erweiterte Notation für reguläre Ausdrücke bieten.

Dave Clarke
quelle
2
Antimirov ist eine nicht deterministische Variante von Brzozowski.
Sylvain
Der Name kam mir sicher bekannt vor.
Dave Clarke
danke für den 'überarbeiteten' Artikel, das hatte ich nicht gesehen!
s8soj3o289