Geodesic
On reducibilities of numerations
Sbornik. Mathematics, Tome 40 (1981) no. 2, pp. 193-204 
A. N. Degtev. On reducibilities of numerations. Sbornik. Mathematics, Tome 40 (1981) no. 2, pp. 193-204. http://geodesic.mathdoc.fr/item/SM_1981_40_2_a4/
@article{SM_1981_40_2_a4,
     author = {A. N. Degtev},
     title = {On reducibilities of numerations},
     journal = {Sbornik. Mathematics},
     pages = {193--204},
     year = {1981},
     volume = {40},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SM_1981_40_2_a4/}
}
TY  - JOUR
AU  - A. N. Degtev
TI  - On reducibilities of numerations
JO  - Sbornik. Mathematics
PY  - 1981
SP  - 193
EP  - 204
VL  - 40
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/SM_1981_40_2_a4/
LA  - en
ID  - SM_1981_40_2_a4
ER  - 
%0 Journal Article
%A A. N. Degtev
%T On reducibilities of numerations
%J Sbornik. Mathematics
%D 1981
%P 193-204
%V 40
%N 2
%U http://geodesic.mathdoc.fr/item/SM_1981_40_2_a4/
%G en
%F SM_1981_40_2_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

If $\nu_0$ and $\nu_1$ are two numerations of the set $S$, then $\nu_0$ will be said to be $e$-reducible to $\nu_1$ provided there exists an enumeration operator $\Phi$ such that ($\forall s\in S$) $[\nu_0^{-1}(s)=\Phi(\nu_1^{-1}(s))]$. In this paper both $e$-reducibility and upper semilattices of $e$-equivalent computable families of recursively enumerable sets are studied. Some of these semilattices admit an elegant description; for others sufficient conditions are found in order that they have an $e$-principal numeration or be countable. Bibliography: 7 titles.

[1] Yu. L. Ershov, Teoriya numeratsii, izd-vo “Nauka”, Moskva, 1977 | MR

[2] E. A. Polyakov, M. G. Rozinas, Teoriya algoritmov, Ivanovo, 1976 | MR

[3] F. I. Validov, “O minimalnykh numeratsiyakh semeistv obscherekursivnykh funktsii”, Izv. VUZov, Matematika, 1978, no. 9, 13–24 | MR | Zbl

[4] A. B. Khutoretskii, “O svodimostyakh vychislimykh numeratsii”, Algebra i logika, 1969, no. 2, 251–264

[5] A. H. Lachlan, “Lower bounds for pairs of r. e. degrees”, Proc. London Math. Soc., 16 (1966), 537–569 | DOI | MR | Zbl

[6] C. Jockusch, “Semirecursive sets and positive reducibility”, Trans. Amer. Math. Soc., 131 (1968), 420–436 | DOI | MR | Zbl

[7] Dzh. Shenfild, Stepeni nerazreshimosti, izd-vo “Nauka”, Moskva, 1977 | MR