Таксономия известных автоматов регулярных выражений

10

Я пытаюсь составить таксономию алгоритмов для преобразования регулярных выражений в автоматы, чтобы выполнить некоторые эмпирические тесты их свойств сложности в определенных областях.

Я знаю несколько «больших» имен, например:

Томпсон

«Алгоритм поиска регулярных выражений», Томпсон, 1968

Глушков

«Новый квадратичный алгоритм для преобразования регулярного выражения в автомат», Ponty, et. Аль, 1996

Антимиров

«Частичные производные регулярных выражений и конструкции конечных автоматов», Антимиров, 1996

следить

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

«Вычисление следующего автомата выражения», Champarnaud, et. 2002 год

Hromkovic

«Перевод регулярных выражений в малые недетерминированные конечные автоматы, свободные от электронных», Hromkovic, et. 2001 год

и их отличительные свойства (отсутствие эпсилон-ности, детерминизм, размер, минимизация и т. д.), но я знаю, что это не исчерпывающий список.

Меня особенно интересуют алгоритмы, которые представляют либо существенно отличающиеся временные сложности от перечисленных выше, и / или существенно отличающиеся топологии.

Если вы знаете о других, ссылка на документ , который описывает алгоритм построения в деталях было бы весьма признателен (читай необходимо , если я собираюсь реализовать это!)

Изменить: Добавлено несколько ссылок в соответствии с просьбой.

automata-theory fl.formal-languages regular-expressions s8soj3o289
источник
@Radu GRIGore Я добавил несколько ссылок. Это лучшие ссылки, которые я знаю об этих автоматах, но могут быть и другие.
s8soj3o289
1
Для Глушкова моя обычная ссылка - Дж. Берстель и Ж.-Е. Пин, «Местные языки и алгоритм Берри – Сетхи», 1996.
Сильвен,
1
Кстати, вы можете найти реализации некоторых из этих алгоритмов в библиотеке Vaucanson C ++ для справки по созданию этих алгоритмов. trac.lrde.org/vaucanson/browser/include/vaucanson/algorithms (в котором standard_of = Глушков, thompson_of = Томпсон, производный_term_automaton = Антимиров, Бжозовский = Бжозовский)
Микаэль Кадилхац,
@ michael-cadilhac Спасибо за указатель. Жаль, что я знал об этом, прежде чем я сам внедрил другие! Я обязательно посмотрю.
s8soj3o289

Ответы:

7

Уотсон (Tech. Rep. Univ. Eindhoven 1995) написал таксономию алгоритмов построения конечных автоматов; несколько более недавних событий найдены ниже.

Для NFA с эпсилон-переходами в книге теории разбора Sippu / Soisalon-Soininen (Springer, 1998) содержится вариант построения Томпсона. Илие и Ю (I & C 2003) и Гулан и Фернэу (FSTTCS 2008) дают усовершенствованные версии классической конструкции. Минимальный требуемый размер эпсилон-НФА, соответствующий регулярным выражениям, дополнительно изучен Грубером и Гуланом (LATA 2010). Структура лежащих в основе орграфов, полученных в результате построения Томпсона, изучена Джаммаррези, Понти, Вудом и Зиади (Discr. Appl. Math 2004) и Гуланом (Tech. Rep. Univ. Trier, 2010).

Что касается свободных от эпсилона NFAs, я хочу упомянуть более раннюю работу Berry & Sethi (TCS 1986) и Brüggemann-Klein (TCS 1993), но это, вероятно, охватывается таксономией Ватсона.

N⋅2О(журнал*⁡N)

Также обратите внимание: что касается быстрых алгоритмов сопоставления регулярных выражений, мне известны недавние работы Билла и Торапа (ICALP 2009, SODA 2010). Они используют классическую конструкцию Томпсона (плюс, конечно, множество трюков для получения скорости).

Герман Грубер
источник
1
это отличный ответ, большое спасибо. я вижу, вы также недавно опубликовали книгу на эту тему - могу ли я также спросить, а. он доступен онлайн в любой форме, и b. или вы когда-нибудь рассматривали сложность «среднего случая» для конкретных доменов? Я в первую очередь заинтересован в приложениях к NLP, где некоторые пока еще в значительной степени неподтвержденные данные свидетельствуют о том, что сложность среднего из этих алгоритмов в значительной степени отличается от сценариев наихудшего случая, описанных в литературе по CS.
s8soj3o289
Также я не совсем уверен, что диктует этикет с точки зрения выбора ответа. Ваш ответ явно превосходит тот, который я выбрал ранее.
s8soj3o289
Только тизер книги доступен онлайн бесплатно.
Герман Грубер
Что касается средней сложности состояния дел, есть также статья о среднем размере NFA для конечных языков с М. Хольцером (TCS 2007); но больше всего похоже на работу Никао о автоматах Глушкова (LATA 2009); есть также готовящаяся статья Nicaud, Pivoteau & Razet (FSTTCS 2010) с интересным названием - я еще не смог взглянуть.
Герман Грубер
Gouveia, Moreira & Reis (CiE 2010) проводят эксперименты по преобразованию RE в NFA. Broda, Machiavelo, Moreira & Reis (DLT 2010) сравнивают количество автоматов положения (Глушков) и автоматов уравнения (Антимиров) в среднем. Это может быть также интересно.
Герман Грубер
5

В вашем списке не учитываются производные регулярных выражений от Janusz Brzozowski, Journal of ACM 1964, недавно пересмотренные Скоттом Оуэнсом, Джоном Реппи и Аароном Туроном в пересмотренных производных регулярных выражений. Журнал функционального программирования (2009), 19: 173-190 , которые обеспечивают практическую реализацию техники для расширенной записи регулярных выражений.

Дэйв Кларк
источник
2
Антимиров является недетерминированным вариантом Бжозовского.
Сильвен
Название, конечно, звучало знакомо.
Дейв Кларк
спасибо за «переосмотренную» статью, я этого не видел!
s8soj3o289