Информационная система "Конференции"

Тезисы докладов

вычислительная математика

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

Целью работы является построение т.н. anytime-алгоритма (псевдооптимального алгоритма реального времени) вершинной минимизации недетерминированных конечных атоматов Рабина-Скотта (НРС-автоматов).

В работе использвался незавершенный метод ветвей и границ с применением комбинаций эвристик как для вычисления границ так и для выбора элементов для последующего ветвления алгоритма.

Алгоритм из всего множества блоков таблицы отношений некоего регулярного языка (таблицы бинарного отношения $#$, определенного в [1], тамже даны и остальные определения) выбирает оптимальное (с т.з. алгоритма, т.е. псевдооптимальное) по количеству элементов подмножетсво. Получаемое блоков удовлетворяет условиям необходимости того, что оно определяет псевдооптимальный по числу вершин НРС-автомат.

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

1. B.Melnikov Once more about the state-minimization of the nondeterministic finite automata -- The Korean Journal of Computational and Applied Mathematics Vol.~7, No.~3 (2000) 655--662.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2005, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2005, Сибирское отделение Российской академии наук, Новосибирск