Categoricity for Primitive Recursive and Polynomial Boolean Algebras

Standard

Categoricity for Primitive Recursive and Polynomial Boolean Algebras. / Alaev, P. E.

In: Algebra and Logic, Vol. 57, No. 4, 01.09.2018, p. 251-274.

Research output: Contribution to journal › Article › peer-review

Harvard

Alaev, PE 2018, 'Categoricity for Primitive Recursive and Polynomial Boolean Algebras', Algebra and Logic, vol. 57, no. 4, pp. 251-274. https://doi.org/10.1007/s10469-018-9498-1

APA

Alaev, P. E. (2018). Categoricity for Primitive Recursive and Polynomial Boolean Algebras. Algebra and Logic, 57(4), 251-274. https://doi.org/10.1007/s10469-018-9498-1

Vancouver

Alaev PE. Categoricity for Primitive Recursive and Polynomial Boolean Algebras. Algebra and Logic. 2018 Sept 1;57(4):251-274. doi: 10.1007/s10469-018-9498-1

Author

Alaev, P. E. / Categoricity for Primitive Recursive and Polynomial Boolean Algebras. In: Algebra and Logic. 2018 ; Vol. 57, No. 4. pp. 251-274.

BibTeX

@article{137b7a3766854047acc51b610c7a673f,

title = "Categoricity for Primitive Recursive and Polynomial Boolean Algebras",

abstract = "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.",

keywords = "Boolean algebra, Boolean algebra computable in polynomial time, computable presentation, primitive recursively categorical Boolean algebra, COMPLEXITY, TIME",

author = "Alaev, {P. E.}",

note = "Publisher Copyright: {\textcopyright} 2018, Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2018",

month = sep,

day = "1",

doi = "10.1007/s10469-018-9498-1",

language = "English",

volume = "57",

pages = "251--274",

journal = "Algebra and Logic",

issn = "0002-5232",

publisher = "Springer US",

number = "4",

}

RIS

TY - JOUR

T1 - Categoricity for Primitive Recursive and Polynomial Boolean Algebras

AU - Alaev, P. E.

PY - 2018/9/1

Y1 - 2018/9/1

N2 - 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.

AB - 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.

KW - Boolean algebra

KW - Boolean algebra computable in polynomial time

KW - computable presentation

KW - primitive recursively categorical Boolean algebra

KW - COMPLEXITY

KW - TIME

UR - http://www.scopus.com/inward/record.url?scp=85056902083&partnerID=8YFLogxK

U2 - 10.1007/s10469-018-9498-1

DO - 10.1007/s10469-018-9498-1

M3 - Article

AN - SCOPUS:85056902083

VL - 57

SP - 251

EP - 274

JO - Algebra and Logic

JF - Algebra and Logic

SN - 0002-5232

IS - 4

ER -

ID: 17515544