Categoricity for Primitive Recursive and Polynomial Boolean Algebras | Sciact - Система учета научной деятельности ИМ СО РАН

Categoricity for Primitive Recursive and Polynomial Boolean Algebras Научная публикация

Журнал

Algebra and Logic
ISSN: 0002-5232 , E-ISSN: 1573-8302

Вых. Данные

Год: 2018, Том: 57, Номер: 4, Страницы: 251-274 Страниц : 24 DOI: 10.1007/s10469-018-9498-1

Ключевые слова

Boolean algebra; Boolean algebra computable in polynomial time; computable presentation; primitive recursively categorical Boolean algebra

Авторы

Alaev P.E. ^1,2

Организации

1	Sobolev Institute of Mathematics, pr. Akad. Koptyuga 4, Novosibirsk, 630090, Russian Federation
2	Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090, Russian Federation

We define a class KΣ of primitive recursive structures whose existential diagram is decidable with primitive recursive witnesses. It is proved that a Boolean algebra has a presentation in KΣ iff it has a computable presentation with computable set of atoms. Moreover, such a Boolean algebra is primitive recursively categorical with respect to KΣ iff it has finitely many atoms. The obtained results can also be carried over to Boolean algebras computable in polynomial time. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.

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

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

Web of science:	WOS:000452074900001
Scopus:	2-s2.0-85056902083
OpenAlex:	W2901392137

БД	Цитирований
Scopus	12
OpenAlex	12
Web of science	11