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