RUS  ENG
Полная версия
ЖУРНАЛЫ // Сибирский математический журнал // Архив

Сиб. матем. журн., 2026, том 67, номер 5, страницы 1007–1019 (Mi smj8073)

Вычислимые изоморфизмы относительно регулярных булевых алгебр

И. Н. Шиманоговa, М. Н. Вялыйabc

a Московский физико-технический институт (национальный исследовательский университет), ул. Керченская, 1А, корп. 1, Москва 117303
b Федеральный исследовательский центр «Информатика и управление» Российской академии наук, ул. Вавилова, 44, корп. 2, Москва 119333
c Национальный исследовательский университет «Высшая школа экономики», Покровский б-р., 11, Москва 109028

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

Ключевые слова: задачи регулярной реализуемости, булевы алгебры, относительно регулярные алгебры, вычислительная сложность, регулярные языки.

УДК: 519.713.2+512.563

MSC: 35R30

Статья поступила: 10.12.2025
Окончательный вариант: 18.06.2026
Принята к печати: 24.06.2026

DOI: 10.33048/smzh.2026.67.519


 Англоязычная версия: Siberian Mathematical Journal, 2026, 67:5, 1203–1212


© МИАН, 2026