Geodesic
Complexity properties of recursively enumerable sets and $sQ$-completeness
Matematičeskie zametki, Tome 62 (1997) no. 3, pp. 425-429 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The notions of effectively subcreative set and strongly effectively acceleratable set are introduced. It is proved that the notions of effectively subcreative set, strongly effectively acceleratable set, and $sQ$-complete recursively enumerable set are equivalent. 
@article{MZM_1997_62_3_a10,
     author = {R. Sh. Omanadze},
     title = {Complexity properties of recursively enumerable sets and $sQ$-completeness},
     journal = {Matemati\v{c}eskie zametki},
     pages = {425--429},
     year = {1997},
     volume = {62},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/}
}
TY  - JOUR
AU  - R. Sh. Omanadze
TI  - Complexity properties of recursively enumerable sets and $sQ$-completeness
JO  - Matematičeskie zametki
PY  - 1997
SP  - 425
EP  - 429
VL  - 62
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/
LA  - ru
ID  - MZM_1997_62_3_a10
ER  - 
%0 Journal Article
%A R. Sh. Omanadze
%T Complexity properties of recursively enumerable sets and $sQ$-completeness
%J Matematičeskie zametki
%D 1997
%P 425-429
%V 62
%N 3
%U http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/
%G ru
%F MZM_1997_62_3_a10
R. Sh. Omanadze. Complexity properties of recursively enumerable sets and $sQ$-completeness. Matematičeskie zametki, Tome 62 (1997) no. 3, pp. 425-429. http://geodesic.mathdoc.fr/item/MZM_1997_62_3_a10/

[1] Blum M., Marques I., “Complexity properties of recursively enumerable sets”, J. Symbolic Logic, 38:4 (1973), 579–593 | DOI | MR

[2] Gill J. T., Morris P. H., “On subcreative sets and $s$-reducibility”, J. Symbolic Logic, 39:4 (1974), 669–677 | DOI | MR

[3] Rodzhers Kh., Teoriya rekursivnykh funktsii i effektivnaya vychislimost, Mir, M., 1972

[4] Blum M., “A machine-independent theory of the complexity of recursive functions”, J. Assoc. Comput. Mach., 14 (1967), 322–336 | MR | Zbl

[5] Omanadze R. Sh., “Slozhnostnye svoistva rekursivno perechislimykh mnozhestv i $sQ$-polnye mnozhestva”, Soobsch. AN Gruzii, 146:1 (1992), 9–12 | MR | Zbl

[6] Friedberg R. M., Rogers H., “Reducibility and completeness for sets of integers”, Z. Math. Logik Grundlag. Math., 5 (1959), 117–125 | DOI | MR | Zbl

[7] Bulitko V. K., “O sposobakh kharakterizatsii polnykh mnozhestv”, Izv. AN SSSR. Ser. matem., 55:2 (1991), 227–253 | MR | Zbl