Программное исследование объединения полурешёток на множестве подмножеств гридов языка Ватерлоо
Аннотация
Актуальность. Актуальность рассматриваемой предметной области обусловлена необходимостью исследования множества регулярных языков и, в частности, описания различных их подклассов. Также актуальны задачи, которые могут возникать в некоторых подклассах. Это даст, среди прочего, возможность описания новых алгоритмов эквивалентного преобразования недетерминированных конечных автоматов.
Цель исследования. Целью является исследование множества подмножеств гридов языка Ватерлоо с точки зрения абстрактной алгебры.
Материалы и методы. Исследование проводилось с применением библиотеки для работы с недетерминированными конечными автоматами NFALib, реализованной одним из авторов на языке C#, а также статистических методов анализа алгоритмов.
Результаты. Результатами являются закономерности, полученные при рассмотрении полурешёток на множестве подмножеств гридов языка Ватерлоо.
Выводы. Из полученных результатов следует, что минимальный покрывающий автомат, эквивалентный автомату Ватерлоо, можно получить, добавив к минимальному покрывающему множеству гридов один дополнительный. Проведённые расчёты также показывают, что кроме минимального покрывающего автомата можно получить ещё 4 минимальных покрывающих автомата, эквивалентных исходному автомату Ватерлоо, однако для получения каждого из них необходимо заменить 1 или 2 грида, входящих в минимальное покрывающее множество.
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Редакционная политика журнала основывается на традиционных этических принципах российской научной периодики и строится с учетом этических норм работы редакторов и издателей, закрепленных в Кодексе поведения и руководящих принципах наилучшей практики для редактора журнала (Code of Conduct and Best Practice Guidelines for Journal Editors) и Кодексе поведения для издателя журнала (Code of Conduct for Journal Publishers), разработанных Комитетом по публикационной этике - Committee on Publication Ethics (COPE). В процессе издательской деятельности редколлегия журнала руководствуется международными правилами охраны авторского права, нормами действующего законодательства РФ, международными издательскими стандартами и обязательной ссылке на первоисточник.
Журнал позволяет авторам сохранять авторское право без ограничений. Журнал позволяет авторам сохранить права на публикацию без ограничений.
Издательская политика в области авторского права и архивирования определяются «зеленым цветом» в базе данных SHERPA/RoMEO.
Все статьи распространяются на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная, которая позволяет другим использовать, распространять, дополнять эту работу с обязательной ссылкой на оригинальную работу и публикацию в этом журналe.