RUS  ENG
Full version
JOURNALS // Sibirskii Matematicheskii Zhurnal // Archive

Sibirsk. Mat. Zh., 2006 Volume 47, Number 2, Pages 352–360 (Mi smj860)

This article is cited in 1 paper

Complexity of some natural problems on the class of computable $I$-algebras

N. T. Kogabaev

Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: We study computable Boolean algebras with distinguished ideals ($I$-algebras for short). We prove that the isomorphism problem for computable $I$-algebras is $\Sigma_1^1$-complete and show that the computable isomorphism problem and the computable categoricity problem for computable $I$-algebras are $\Sigma_3^0$-complete.

Keywords: computable Boolean algebra with distinguished ideals, computable isomorphism, computably categorical structure, arithmetical complexity, analytical complexity.

UDC: 510.53, 512.563

Received: 01.02.2005


 English version:
Siberian Mathematical Journal, 2006, 47:2, 291–297

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025