Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Bounded Reducibility for Computable Numberings. / Bazhenov, Nikolay; Mustafa, Manat; Ospichev, Sergei.
Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. ред. / Florin Manea; Barnaby Martin; Daniël Paulusma; Giuseppe Primiero. Springer-Verlag GmbH and Co. KG, 2019. стр. 96-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 11558 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Bounded Reducibility for Computable Numberings
AU - Bazhenov, Nikolay
AU - Mustafa, Manat
AU - Ospichev, Sergei
PY - 2019/1/1
Y1 - 2019/1/1
N2 - The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility ≤ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family S of c.e. sets, its Rogers semilattice R(S) contains the ≤ -degrees of computable numberings of S. Khutoretskii proved that R(S) is always either one-element, or infinite. Selivanov proved that an infinite R(S) cannot be a lattice. We introduce a bounded version of reducibility between numberings, denoted by ≤ bm. We show that Rogers semilattices Rbm(S), induced by ≤ bm, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number n≥ 2, there is a finite family S of c.e. sets such that its semilattice Rbm(S) has precisely 2 n- 1 elements. Furthermore, there is a computable family T of c.e. sets such that Rbm(T) is an infinite lattice.
AB - The theory of numberings gives a fruitful approach to studying uniform computations for various families of mathematical objects. The algorithmic complexity of numberings is usually classified via the reducibility ≤ between numberings. This reducibility gives rise to an upper semilattice of degrees, which is often called the Rogers semilattice. For a computable family S of c.e. sets, its Rogers semilattice R(S) contains the ≤ -degrees of computable numberings of S. Khutoretskii proved that R(S) is always either one-element, or infinite. Selivanov proved that an infinite R(S) cannot be a lattice. We introduce a bounded version of reducibility between numberings, denoted by ≤ bm. We show that Rogers semilattices Rbm(S), induced by ≤ bm, exhibit a striking difference from the classical case. We prove that the results of Khutoretskii and Selivanov cannot be extended to our setting: For any natural number n≥ 2, there is a finite family S of c.e. sets such that its semilattice Rbm(S) has precisely 2 n- 1 elements. Furthermore, there is a computable family T of c.e. sets such that Rbm(T) is an infinite lattice.
UR - http://www.scopus.com/inward/record.url?scp=85069464896&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-22996-2_9
DO - 10.1007/978-3-030-22996-2_9
M3 - Conference contribution
AN - SCOPUS:85069464896
SN - 9783030229955
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 96
EP - 107
BT - Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
A2 - Manea, Florin
A2 - Martin, Barnaby
A2 - Paulusma, Daniël
A2 - Primiero, Giuseppe
PB - Springer-Verlag GmbH and Co. KG
T2 - 15th Conference on Computability in Europe, CiE 2019
Y2 - 15 July 2019 through 19 July 2019
ER -
ID: 21059091