Программное исследование объединения полурешёток на множестве подмножеств гридов языка Ватерлоо

Аннотация

Актуальность. Актуальность рассматриваемой предметной области обусловлена необходимостью исследования множества регулярных языков и, в частности, описания различных их подклассов. Также актуальны задачи, которые могут возникать в некоторых подклассах. Это даст, среди прочего, возможность описания новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.
Цель исследования. Целью является исследование множества подмножеств гридов языка Ватерлоо с точки зрения абстрактной алгебры.
Материалы и методы. Исследование проводилось с применением библиотеки для работы с недетерминированными конечными автоматами NFALib, реализованной одним из авторов на языке C#, а также статистических методов анализа алгоритмов.
Результаты. Результатами являются закономерности, полученные при рассмотрении полурешёток на множестве подмножеств гридов языка Ватерлоо.
Выводы. Из полученных результатов следует, что минимальный покрывающий автомат, эквивалентный автомату Ватерлоо, можно получить, добавив к минимальному покрывающему множеству гридов один дополнительный. Проведённые расчёты также показывают, что кроме минимального покрывающего автомата можно получить ещё 4 минимальных покрывающих автомата, эквивалентных исходному автомату Ватерлоо, однако для получения каждого из них необходимо заменить 1 или 2 грида, входящих в минимальное покрывающее множество.

Сведения об авторах

Mikhail Eduardovich Abramyan, Южный федеральный университет

доцент Института математики, механики и компьютерных наук им. И.И. Воровича, кандидат физико-математических наук, доцент

Boris Feliksovich Melnikov, Совместный университет МГУ-ППИ в Шэньчжэне

профессор факультета вычислительной математики и кибернетики, доктор физико-математических наук, профессор

Опубликована
2023-10-15
Как цитировать
ABRAMYAN, Mikhail Eduardovich; MELNIKOV, Boris Feliksovich. Программное исследование объединения полурешёток на множестве подмножеств гридов языка Ватерлоо. Современные информационные технологии и ИТ-образование, [S.l.], v. 19, n. 3, oct. 2023. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/1012>. Дата доступа: 22 apr. 2024
Раздел
Теоретические вопросы информатики, прикладной математики, компьютерных наук

Наиболее читаемые статьи этого автора (авторов)