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

Авторы

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

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

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

Аннотация

Рассматривается задача построения регулярного выражения с минимальной звёздной высотой для заданного недетерминированного конечного автомата. Предлагается 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.

Загрузки

Выпуск

№ 3 (13) (2010)

Раздел

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

Лицензия

Авторы, публикующие статьи в журнале «Вектор науки Тольяттинского государственного университета», соглашаются на следующее:

1. Автор, направляя рукопись в редакцию журнала «Вектор науки Тольяттинского государственного университета», соглашается с тем, что Редакции переходят исключительные имущественные права на использование статьи (переданного в редакцию журнала материала, в т. ч. такие охраняемые объекты авторского права, как рисунки, схемы, таблицы и т. п.), в том числе на воспроизведение в печати и в сети Интернет; на распространение; на перевод материалов на английский язык.

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

Редакция не несет ответственности перед третьими лицами за нарушение данных Автором гарантий.

3. За Автором сохраняется право использования его опубликованного материала, его фрагментов и частей в личных, в том числе научных, преподавательских, целях. Перепечатка материалов, опубликованных в журнале, другими физическими и юридическими лицами возможна только с письменного согласия Редакции, с обязательным указанием номера журнала (года издания), в котором был опубликован материал.