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

Sibirsk. Mat. Zh., 2002 Volume 43, Number 4, Pages 769–778 (Mi smj1328)

This article is cited in 18 papers

Minimal coverings in the Rogers semilattices of $\Sigma_n^0$-computable numberings

S. A. Badaeva, S. Yu. Podzorovb

a Al-Farabi Kazakh National University, Faculty of Mechanics and Mathematics
b Sobolev Institute of Mathematics, Siberian Branch of the Russian Academy of Sciences

Abstract: Under study is the problem of existence of minimal and strong minimal coverings in Rogers semilattices of $\Sigma_n^0$-computable numberings for $n\ge 2$. Two sufficient conditions for existence of minimal coverings and one sufficient condition for existence of strong minimal coverings are found. The problem is completely solved of existence of minimal coverings in Rogers semilattices of $\sum_n^0$-computable numberings of a finite family.

Keywords: computability, numbering, Rogers semilattice, minimal covering.

UDC: 510.5

Received: 29.03.2001


 English version:
Siberian Mathematical Journal, 2002, 43:4, 616–622

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024