Taksonomia znaczących automatów wyrażeń regularnych

Próbuję opracować systematykę algorytmów do przekształcania wyrażeń regularnych w automaty, aby przeprowadzić pewne testy empiryczne ich właściwości złożoności w określonych domenach.

Znam kilka „większych” nazw, np.

Thompson

„Algorytm wyszukiwania wyrażeń regularnych”, Thompson, 1968

Glushkov

„Nowy algorytm kwadratowy do przekształcenia wyrażenia regularnego w automat”, Ponty i in. al. 1996

Antimirov

„Częściowe pochodne wyrażeń regularnych i konstrukcji automatów skończonych”, Antimirov, 1996

Podążać

„Follow Automata”, Ilie i in. al, 2003;

„Obliczanie automatycznego automatu wyrażenia”, Champarnaud i in. al. 2002

Hromković

„Tłumaczenie wyrażeń regularnych na małe niedeterministyczne, skończone automaty e-wolne”, Hromkovic i in. al, 2001

i ich wyróżniające właściwości (bez epsilonu, determinizm, rozmiar, minimalizacja itp.), ale wiem, że nie jest to wyczerpująca lista.

Szczególnie interesują mnie algorytmy, które prezentują albo znacznie inne złożoności czasowe niż te wymienione powyżej i / lub znacząco różne topologie.

Jeśli znasz innych, bardzo doceniony zostanie link do artykułu opisującego szczegółowo algorytm konstrukcyjny (przeczytaj, jeśli zamierzam go wdrożyć!)

Edycja: Dodano niektóre referencje zgodnie z żądaniem.

automata-theory fl.formal-languages regular-expressions s8soj3o289
źródło

@Radu GRIGore Dodałem kilka referencji. To najlepsze referencje, jakie znam dla tych automatów, ale mogą być też inne.

s8soj3o289,

W przypadku Głuszkowa moje zwykłe odniesienia to J. Berstel i J.-E. Pin, „Lokalne języki i algorytm Berry – Sethi”, 1996.

Sylvain,

Nawiasem mówiąc, możesz znaleźć implementacje niektórych z tych algorytmów w bibliotece Vaucanson C ++, w celu uzyskania informacji na temat konstruowania tych algorytmów. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (w których standard_of = Glushkov, thompson_of = Thompson, pochodna_term_automaton = Antimirov, brzozowski = Brzozowski)

Michaël Cadilhac

@ michael-cadilhac Dzięki za wskaźnik. Chciałbym wiedzieć o tym, zanim sam zrealizowałem pozostałe! Na pewno się obejrzę.

s8soj3o289,

Odpowiedzi:

Watson (Tech. Rep. Univ. Eindhoven 1995) napisał taksonomię algorytmów konstrukcji automatów skończonych; kilka najnowszych zmian znajduje się poniżej.

W przypadku NFA z przejściami epsilon książka teorii parsowania autorstwa Sippu / Soisalon-Soininen (Springer, 1998) zawiera wariant konstrukcji Thompsona. Ilie i Yu (I&C 2003) oraz Gulan i Fernau (FSTTCS 2008) podają wyrafinowane wersje klasycznej konstrukcji. Minimalny wymagany rozmiar epsilon-NFA odpowiadających wyrażeniom regularnym jest dalej badany przez Gruber i Gulan (LATA 2010). Strukturę leżących u podstaw digrafów wynikających z konstrukcji Thompsona badają Giammarresi, Ponty, Wood & Ziadi (Discr. Appl. Math 2004) i Gulan (Tech. Rep. Univ. Trier, 2010).

Jeśli chodzi o NFA wolne od epsilonu, chcę wspomnieć o wcześniejszej pracy Berry'ego i Sethi (TCS 1986) i Brüggemann-Klein (TCS 1993), ale prawdopodobnie jest to objęte taksonomią Watsona.

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

Uwaga: Jeśli chodzi o szybkie algorytmy dopasowywania wyrażeń regularnych, jestem świadomy ostatnich prac Bille i Thorup (ICALP 2009, SODA 2010). Używają klasycznej konstrukcji Thompsona (plus oczywiście wiele sztuczek, aby uzyskać szybkość).

Hermann Gruber
źródło

to świetna odpowiedź, dziękuję bardzo. Widzę, że niedawno opublikowałeś książkę na ten temat - czy mogę również zapytać, czy. jest dostępny on-line w dowolnej formie, ib. czy tak, czy kiedykolwiek zastanawiałeś się nad złożonością „przeciętnego przypadku” dla określonych domen? Interesują mnie przede wszystkim aplikacje, w których niektóre, jak dotąd w dużej mierze niepotwierdzone dowody, sugerują, że średnia złożoność niektórych algorytmów różni się znacznie od najgorszych scenariuszy opisanych w literaturze cs.

s8soj3o289,

Nie jestem też do końca pewien, co dyktuje etyka, jeśli chodzi o wybór odpowiedzi. twoja odpowiedź jest wyraźnie lepsza od tej, którą wcześniej wybrałem.

s8soj3o289,

Tylko zwiastun książki jest dostępny online za darmo.

Hermann Gruber

Jeśli chodzi o średnią złożoność stanu sprawy, istnieje również papier o średnim rozmiarze NFA dla języków skończonych z M. Holzerem (TCS 2007); ale najbardziej pokrewna wydaje się praca Nicauda nad automatami Glushkov (LATA 2009); nadchodzi także artykuł Nicaud, Pivoteau & Razet (FSTTCS 2010) o ciekawym tytule - jeszcze nie byłem w stanie rzucić okiem.

Hermann Gruber

Gouveia, Moreira i Reis (CiE 2010) przeprowadzają eksperymenty dotyczące konwersji RE do NFA. Broda, Machiavelo, Moreira i Reis (DLT 2010) porównują średnio liczbę stanów automatów pozycji (Glushkov) i automatów równań (Antimirov). To może być również interesujące.

Hermann Gruber

Jednym z nieuwzględnionych na twojej liście są Pochodne wyrażeń regularnych autorstwa Janusza Brzozowskiego, Journal of ACM 1964, ostatnio ponownie przeanalizowane przez Scotta Owensa, Johna Reppy'ego i Aarona Turona w pochodnych wyrażeń regularnych ponownie zbadanych. Journal of Functional Programming (2009), 19: 173-190 , którzy zapewniają praktyczną implementację techniki rozszerzonej notacji dla wyrażeń regularnych.

Dave Clarke
źródło

Antimirov to niedeterministyczny wariant Brzozowskiego.

Sylvain,

Nazwa z pewnością brzmiała znajomo.

Dave Clarke

dzięki za artykuł „ponownie zbadany”, nie widziałem tego!

s8soj3o289,