Geodesic
$m$-Reducibility with Upper and Lower Bounds for the Reducing Functions
Matematičeskie zametki, Tome 70 (2001) no. 1, pp. 12-21 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

We study pairs $(\mathfrak T^1,\mathfrak T^0)$ of classes of nondecreasing total one-place arithmetic functions that specify reflexive and transitive binary relations $\{(A,B)\mid A,B\subseteq N\mathop{\&}(\exists$ g.r.f. $h$) $(\exists f_1\in \mathfrak T^0)[A\le{}_m^hB\mathop{\&}f_0\trianglelefteq h\trianglelefteq f_1]\}$. (Here $k\trianglelefteq l$ means that the function $l$ majorizes the function $k$ almost everywhere.) Criteria for reflexivity and transitivity of such relations are established. Evidence of extensive branching of the arising system of bounded $m$-reducibilities is obtained. We construct examples of such reducibilities that essentially differ from the standard $m$-reducibility in the structure of systems of undecidability degrees that they generate and in the question of completeness of sets. 
@article{MZM_2001_70_1_a1,
     author = {V. N. Belyaev and V. K. Bulitko},
     title = {$m${-Reducibility} with {Upper} and {Lower} {Bounds} for the {Reducing} {Functions}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {12--21},
     year = {2001},
     volume = {70},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2001_70_1_a1/}
}
TY  - JOUR
AU  - V. N. Belyaev
AU  - V. K. Bulitko
TI  - $m$-Reducibility with Upper and Lower Bounds for the Reducing Functions
JO  - Matematičeskie zametki
PY  - 2001
SP  - 12
EP  - 21
VL  - 70
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/MZM_2001_70_1_a1/
LA  - ru
ID  - MZM_2001_70_1_a1
ER  - 
%0 Journal Article
%A V. N. Belyaev
%A V. K. Bulitko
%T $m$-Reducibility with Upper and Lower Bounds for the Reducing Functions
%J Matematičeskie zametki
%D 2001
%P 12-21
%V 70
%N 1
%U http://geodesic.mathdoc.fr/item/MZM_2001_70_1_a1/
%G ru
%F MZM_2001_70_1_a1
V. N. Belyaev; V. K. Bulitko. $m$-Reducibility with Upper and Lower Bounds for the Reducing Functions. Matematičeskie zametki, Tome 70 (2001) no. 1, pp. 12-21. http://geodesic.mathdoc.fr/item/MZM_2001_70_1_a1/

[1] Bulitko V. K., “Subtyuringovy svodimosti ogranichennoi slozhnosti”, Izv. vuzov. Matem., 1992, no. 1, 27–37 | MR | Zbl

[2] Bulitko V. K., “About Segment Complexity of Turing Reductions”, Math. Log. Quart., 45:4 (1999), 561–571 | MR | Zbl

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

[4] Bulitko V. K., “O rekursivno szhimaemykh mnozhestvakh”, Matem. zametki, 64:1 (1998), 9–16 | MR | Zbl