Аннотация:
Рассматривается класс булевых алгебр, образуемых пересечениями регулярных языков с заданным языком. В случае, когда такая алгебра изоморфна алгебре регулярных языков, доказывается существование изоморфизма, вычислимого с использованием оракулов для задачи регулярной реализуемости и бесконечной регулярной реализуемости. Данный результат дает существование вычислимого изоморфизма булевых алгебр регулярных языков над алфавитом из одной буквы и из двух букв. Также строится нижняя оценка сложности этой задачи.
Ключевые слова:
задачи регулярной реализуемости, булевы алгебры, относительно регулярные алгебры, вычислительная сложность, регулярные языки.