Abstract: В статье определяется класс К, состоящий из примитивно рекурсивных структур, в которых экзистенциальная диаграмма разрешима с примитивно рекурсивными свидетелями. Доказано, что булева алгебра обладает представлением из К тогда и только тогда, когда у неё есть вычислимое представление с вычислимым множеством атомов. Доказано, что такая булева алгебра примитивно рекурсивно категорична относительно К тогда и только тогда, когда число атомов в ней конечно. Полученные результаты перенесены и на случай булевых алгебр, вычислимых за полиномиальное время.

Cite: Alaev P.E.
Категоричность для примитивно рекурсивных и полиномиальных булевых алгебр
Алгебра и логика. 2018. Т.57. №4. С.389-425.

Translated: 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

Identifiers: No identifiers

Citing: Пока нет цитирований