Categoricity for Primitive Recursive and Polynomial Boolean Algebras

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)251-274
Number of pages24
JournalAlgebra and Logic
Volume57
Issue number4
DOIs
Publication statusPublished - 1 Sep 2018

Keywords

  • Boolean algebra
  • Boolean algebra computable in polynomial time
  • computable presentation
  • primitive recursively categorical Boolean algebra
  • COMPLEXITY
  • TIME

Fingerprint Dive into the research topics of 'Categoricity for Primitive Recursive and Polynomial Boolean Algebras'. Together they form a unique fingerprint.

Cite this