ДОПОЛНИТЕЛЬНЫЕ ЭВРИСТИКИ В ЗАДАЧЕ ЗВЁЗДНО-ВЫСОТНОЙ МИНИМИЗАЦИИ НЕДЕТЕРМИНИРОВАННОГО КОНЕЧНОГО АВТОМАТА

Авторы

  • Светлана Викторовна Баумгертнер Тольяттинский государственный университет

Ключевые слова:

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

Аннотация

Рассматривается задача построения регулярного выражения с минимальной звёздной высотой для заданного недетерминированного конечного автомата. Предлагается anytime-алгоритм, основанный на применении нескольких эвристик.

Библиографические ссылки

1. Б.Мельников. Мультиэвристический подход к задачам дискретной оптимизации. – Кибернетика и системный анализ (НАН Украины), 2006, №3. С. 32–42.
2. Б.Мельников, А.Радионов. О выборе стратегии в недетерминированных антагонистических играх. – Известия РАН. Программирование, 1998, №5, C. 55–62.
3. Б.Мельников, Н.Романов. Ещё раз об эвристиках для задачи коммивояжёра. - В кн.: Теоретические проблемы информатики и ее приложений, вып.4, Саратов, изд-во СГУ, 2001, с.81-92.
4. Б.Мельников. Эвристики в программировании недетерминированных игр. – Известия РАН. Программирование, 2001, №5. С. 63–80.
5. С.Пивнева, О.Рогова: Алгоритм определения репрезентативности недетерминированного конечного автомата. – Электронное научное периодическое изд. «Электроника и информационные технологии» (http://fetmag.mrsu.ru/), 2009, вып.1
6. А. Саломаа. Жемчужины теории формальных языков. – М.: Мир, 1986. – 159 с.
7. K.Hashiguchi. Algorithms for determining relative star height and star height. – Inform. Comput., 78 (1988) 124-169.
8. D.Kirsten. Distance desert automata and the star height problem. – Theoret. Informatics Appl., 39 (2005) 455–509.
9. B.Melnikov, A.Vakhitova. Some more on the finite automata. – The Korean Journal of Computional and Applied Mathematics, Vol.5, №3 (1998) 495–506.

Загрузки

Выпуск

Раздел

Естественные науки