Sciact
  • EN
  • RU

Категоричность для примитивно рекурсивных и полиномиальных булевых алгебр Научная публикация

Журнал Алгебра и логика
ISSN: 0373-9252
Вых. Данные Год: 2018, Том: 57, Номер: 4, Страницы: 389-425 Страниц : 37
Авторы Alaev P.E. 1,2
Организации
1 Институт математики им. С.Л. Соболева СО РАН
2 Новосибирский государственный университет

Реферат: В статье определяется класс К, состоящий из примитивно рекурсивных структур, в которых экзистенциальная диаграмма разрешима с примитивно рекурсивными свидетелями. Доказано, что булева алгебра обладает представлением из К тогда и только тогда, когда у неё есть вычислимое представление с вычислимым множеством атомов. Доказано, что такая булева алгебра примитивно рекурсивно категорична относительно К тогда и только тогда, когда число атомов в ней конечно. Полученные результаты перенесены и на случай булевых алгебр, вычислимых за полиномиальное время.
Библиографическая ссылка: Alaev P.E.
Категоричность для примитивно рекурсивных и полиномиальных булевых алгебр
Алгебра и логика. 2018. Т.57. №4. С.389-425.
Переводная: Alaev P.E.
Categoricity for Primitive Recursive and Polynomial Boolean Algebras
Algebra and Logic. 2018. V.57. N4. P.251-274. DOI: 10.1007/s10469-018-9498-1 WOS Scopus OpenAlex
Идентификаторы БД: Нет идентификаторов
Цитирование в БД: Пока нет цитирований