Geodesic
Reducibility by means of almost polynomial functions
Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 68-78.

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

The aim of the work is to introduce a variant of $m$-reducibility using almost polynomial functions and to study the resulting partially ordered set $\mathcal M_{\mathbb P}$ of the corresponding degrees of undecidability. It is proved that the set $\mathcal M_{\mathbb P}$ has at least a countable number of minimal elements, but has no maximal elements. The set $\mathcal M_{\mathbb P}$ is neither an upper nor a lower semilattice. Each element of the set $\mathcal M_{\mathbb P}$, other than the smallest, can be included in a continuum antichain. We construct a continuum family of pairwise isomorphic initial segments of the set $\mathcal M_{\mathbb P}$, having a countable width and height and intersecting only by the smallest element of the set.
Keywords: $m$-reducibility, almost polynomial functions. 
@article{IVM_2022_12_a4,
     author = {S. S. Marchenkov},
     title = {Reducibility by means of almost polynomial functions},
     journal = {Izvesti\^a vys\v{s}ih u\v{c}ebnyh zavedenij. Matematika},
     pages = {68--78},
     publisher = {mathdoc},
     number = {12},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/}
}
TY  - JOUR
AU  - S. S. Marchenkov
TI  - Reducibility by means of almost polynomial functions
JO  - Izvestiâ vysših učebnyh zavedenij. Matematika
PY  - 2022
SP  - 68
EP  - 78
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/
LA  - ru
ID  - IVM_2022_12_a4
ER  - 
%0 Journal Article
%A S. S. Marchenkov
%T Reducibility by means of almost polynomial functions
%J Izvestiâ vysših učebnyh zavedenij. Matematika
%D 2022
%P 68-78
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/
%G ru
%F IVM_2022_12_a4
S. S. Marchenkov. Reducibility by means of almost polynomial functions. Izvestiâ vysših učebnyh zavedenij. Matematika, no. 12 (2022), pp. 68-78. http://geodesic.mathdoc.fr/item/IVM_2022_12_a4/

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

[2] Degtev A.N., Rekursivno perechislimye mnozhestva i svodimosti tablichnogo tipa, Nauka, Fizmatlit, M., 1998

[3] Odifreddi P., “Strong reducibilities”, Bull. Amer. Math. Soc., 4:1 (1981), 37–86

[4] Kuk S.A., “Slozhnost protsedur vyvoda teorem”, Kiberneticheskii sb. Nov. ser., 1975, no. 12, 5–15

[5] Karp R.M., “Svodimost kombinatornykh problem”, Kiberneticheskii sb. Nov. ser., 1975, no. 12, 16–38

[6] Reina G., “Stepeni avtomatnykh preobrazovanii”, Kiberneticheskii sb. Nov. ser., 1977, no. 14, 95–106

[7] Gordon H.G., “Complete degrees of finite-state transformability”, Inform. and Control, 32 (1976), 169–187

[8] Bairasheva V.R., “Strukturnye svoistva avtomatnykh preobrazovanii”, Izv. vuzov. Matem., 1988, no. 7, 34–39

[9] Marchenkov S.S., “Konechnye nachalnye segmenty verkhnei polureshetki konechno-avtomatnykh stepenei”, Diskret. matem., 1:3 (1989), 96–103

[10] Solovev V.D., “Struktura raspredeleniya informatsii v beskonechnoi posledovatelnosti”, Diskret. matem., 8:2 (1996), 97–107

[11] Marchenkov S.S., “Buleva svodimost”, Diskret. matem., 15:3 (2003), 40–53

[12] Marchenkov S.S., Matveev S.A., “Bulevy stepeni, opredelyaemye klassami lineinykh funktsii i kon'yunktsii”, Matem. voprosy kibernet., 14, Fizmatlit, M., 2005, 35–48

[13] Marchenkov S.S., “O stroenii chastichno uporyadochennykh mnozhestv bulevykh stepenei”, Diskret. matem., 18:1 (2006), 63–75

[14] Marchenkov S.S., “Polnye i nepolnye bulevy stepeni”, Probl. peredachi inform., 46:4 (2010), 83–90

[15] Marchenkov S.S., “O maksimalnykh i minimalnykh elementakh chastichno uporyadochennykh mnozhestv bulevykh stepenei”, Diskret. analiz i issled. oper., 20:2 (2013), 88–101

[16] Marchenkov S.S., Buleva svodimost i bulevy stepeni, MAKS Press, M., 2020

[17] Jain S., Stephan F., Teutsch J., “Closed left-r.e. sets”, Computability, 6:1 (2012), 1–21