Статьи автора

ЗАДАЧИ РЕГУЛЯРНОЙ РЕАЛИЗУЕМОСТИ ДЛЯ ОПИСАНИЙ КОНЕЧНЫХ ОТНОШЕНИЙ

Номер выпуска 3 от 18.09.2025

Рассмотрены описания конечных отношений на множестве неотрицательных целых чисел в формате, предложенном П. Вольф и Х. Фернау, и связанные с ними задачи регулярной реализуемости. Доказана универсальность этих задач относительно дизъюнктных сводимостей за полиномиальное время для унарных отношений; относительно дизъюнктных сводимостей на полиномиальной памяти для инвариантных бинарных отношений; а также относительно сводимостей по Тьюрингу с NP-оракулом для инвариантных унарных отношений, заданных в унарном алфавите.

15 0