Categoricity for Primitive Recursive and Polynomial Boolean Algebras

Результат исследования: Научные публикации в периодических изданияхстатья

5 Цитирования (Scopus)

Аннотация

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.

Язык оригиналаанглийский
Страницы (с-по)251-274
Число страниц24
ЖурналAlgebra and Logic
Том57
Номер выпуска4
DOI
СостояниеОпубликовано - 1 сен 2018

Fingerprint Подробные сведения о темах исследования «Categoricity for Primitive Recursive and Polynomial Boolean Algebras». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать