|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Алгоритмическая сложность теорий коммутативных алгебр Клинистатья
Статья опубликована в журнале из списка RSCI Web of Science
Статья опубликована в журнале из перечня ВАК- Автор: Кузнецов С.Л.
- Журнал: Известия РАН. Серия математическая
- Том: 88
- Номер: 2
- Год издания: 2024
- Первая страница: 44
- Последняя страница: 79
- DOI: 10.4213/im9480
- Аннотация: Алгебрами Клини называются структуры со сложением, умножением и константами 0 и 1, задающими идемпотентное полукольцо, и операцией итерации Клини. В частном случае ∗-непрерывных алгебр Клини итерация Клини определяется инфинитарным образом как супремум степеней элемента. В работе получены результаты об алгоритмической сложности хорновых теорий (семантического следования из конечных множеств гипотез) коммутативных ∗-непрерывных алгебр Клини. А именно, доказана Π11-полнота их хорновой теории и Π02-полнота ее фрагмента, где в гипотезах нельзя использовать итерацию. Эти результаты являются коммутативными аналогами соответствующих теорем Д. Козена (2002) для общего (некоммутативного) случая. Также получены несколько сопутствующих результатов.
- Добавил в систему: Кузнецов Степан Львович