Эвристический алгоритм уменьшения множества допустимых корней в задаче о нахождении минимального языка
Автор: Портнов А.М.
Журнал: Теория и практика современной науки @modern-j
Рубрика: Основной раздел
Статья в выпуске: 6-2 (12), 2016 года.
Бесплатный доступ
В статье решается проблема нахождения минимального языка для дополненного максимального префиксного кода. Для двух конечных языков можно определить соотношение эквивалентности. Задача проверки эквивалентности двух конечных языков сводится к задаче нахождения их минимальных языков и проверке того, что это один и тот же язык. Одной из подзадач этой проблемы является уменьшение множества корней и, следовательно, вычислительной сложности. Данная статья описывает соответствующий алгоритм и возможные методы его применения.
Эвристические алгоритмы, вычислительная сложность, максимальный префиксный код, минимальный язык, множество корней
Короткий адрес: https://sciup.org/140269432
IDR: 140269432
Список литературы Эвристический алгоритм уменьшения множества допустимых корней в задаче о нахождении минимального языка
- Melnikov В. The equality condition for infinite catenations of two sets of finite words. // Int. J. of Found. of Comp. Sci., Vol. 4, No. 3 (1993) 267-274.
- Алексеева А.Г. Применение итераций конечных языков в алгоритмических задачах теории формальных языков.
- Алексеева А.Г., Мельников Б.Ф. Итерации конечных и бесконечных языков и недетерминированные конечные автоматы. // Вектор науки Тольяттинского Государственного университета, 2011, №3(17), с 30-33.
- Бросалина А. Оценка эвристических алгоритмов построения регулярного выражения по конечному автомату. // Материалы II Международной научно-практической конф. «Компьютерные технологии в наук, производстве, социальных и экономических процессах». Новочеркасск, 2001. - Ч.1 - С. 11.
- Лаллеман Ж. Полугруппы и комбинаторные приложения - М.: Мир, 1985.
- Мельников Б. Алгоритм проверки равенства бесконечных итераций конечных языков. // Вестник Московского университета, сер.15, №4 (1996) 49-54.
- Портнов А.М. Компактное представление максимального префиксного кода в виде списка замен. // сборник Всероссийской научно-практической internet-конференции «Междисциплинарные исследования в области математического моделирования и информатики», 18-19 июня 2013, с. 37-39.
- Портнов А.М., Мельникова Е.А. Алгоритмы построения минимального языка для некоторых конечных языков // сборник статей II Международной научно-практической конференции «Теоретические и практически вопросы развития научной мысли в современном мире», Уфа, 29-30 апреля 2013. - Ч.1 - с. 21-24.
