Об алгоритмах проверки выполнения некоторых бинарных отношений в глобальном надмоноиде свободного моноида

Актуальность и цели. Предметом исследования являются свободные полугруппы и специальные бинарные отношения, заданные на глобальном надмоноиде свободного моноида (свободной полугруппы). Рассматриваются некоторые специальные бинарные отношения на языках (элементах глобального надмоноида), прежде всего так называемое отношение эквивалентности в бесконечности, рассматривавшееся нами в предыдущих работах и, как следует из названия, являющееся отношением эквивалентности. Мы описываем алгоритмы проверки выполнения этих отношений для элементов глобального надмоноида свободного моноида. Также рассматривается специальное отношение порядка на подмножествах множества слов, которое дает язык, минимальный по этому отношению среди всех языков, эквивалентных в бесконечности заданному. Материалы и методы. Используются общие методы анализа и синтеза, а также специальные методы теории формальных языков, методы описания алгоритмов и методы работы с полугруппами, в частности, метод построения морфизма полугруппы. Результаты. Приводятся примеры построения двух языков (двух элементов надмоноида), для которых в надмоноиде выполняется рассматриваемое нами отношение эквивалентности. Наиболее важный результат работы - описание эффективного алгоритма, отвечающего на вопрос, являются ли итерации двух заданных конечных языков эквивалентными в бесконечности. Приведенные алгоритмы и примеры актуальны для прикладных построения специальных вариантов автоматизированного преобразования регулярных грамматических структур и контекстно-свободных грамматик в системах автоматизации построения компиляторов. Выводы. Во многих частных случаях, описанных нами в предыдущих публикациях, аналоги рассмотренных нами алгоритмов являются полиномиальными. Однако в общем случае вопрос о существовании полиномиальных алгоритмов, отвечающих на поставленные в статье вопросы, остается открытым.