RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретный анализ и исследование операций // Архив

Дискретн. анализ и исслед. опер., 2025, том 32, выпуск 4, страницы 213–230 (Mi da1397)

Задачи бесконечной регулярной реализуемости

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

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

Аннотация: Хорошо изученным классом алгоритмических задач являются задачи регулярной реализуемости  — проверки непустоты пересечения регулярного языка с заданным языком. Такая задача имеет естественную алгебраическую интерпретацию  — проверку принадлежности элемента булевой алгебры ядру определённого гомоморфизма. Это мотивирует рассмотрение аналогичной задачи бесконечной регулярной реализуемости  — проверки бесконечности пересечения регулярного языка с заданным. В работе рассматриваются задачи регулярной реализуемости для разрешимых языков и приводится сравнительный анализ сложности задач бесконечной регулярной реализуемости и задач регулярной реализуемости. Библиогр. 22.

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

УДК: 519.713

Статья поступила: 09.12.2024
Переработанный вариант: 20.08.2025
Принята к публикации: 22.09.2025

DOI: 10.33048/daio.2025.32.822



© МИАН, 2026