Standard
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. ed. / Florin Manea; Barnaby Martin; Daniël Paulusma; Giuseppe Primiero. Springer, 2019. p. 96-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11558 LNCS).
Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Harvard
Bazhenov, N, Mustafa, M
& Ospichev, S 2019,
Bounded Reducibility for Computable Numberings. in F Manea, B Martin, D Paulusma & G Primiero (eds),
Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11558 LNCS, Springer, pp. 96-107, 15th Conference on Computability in Europe, CiE 2019, Durham, United Kingdom,
15.07.2019.
https://doi.org/10.1007/978-3-030-22996-2_9
APA
Bazhenov, N., Mustafa, M.
, & Ospichev, S. (2019).
Bounded Reducibility for Computable Numberings. In F. Manea, B. Martin, D. Paulusma, & G. Primiero (Eds.),
Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings (pp. 96-107). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11558 LNCS). Springer.
https://doi.org/10.1007/978-3-030-22996-2_9
Vancouver
Bazhenov N, Mustafa M
, Ospichev S.
Bounded Reducibility for Computable Numberings. In Manea F, Martin B, Paulusma D, Primiero G, editors, Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. Springer. 2019. p. 96-107. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-22996-2_9
Author
Bazhenov, Nikolay ; Mustafa, Manat
; Ospichev, Sergei. /
Bounded Reducibility for Computable Numberings. Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings. editor / Florin Manea ; Barnaby Martin ; Daniël Paulusma ; Giuseppe Primiero. Springer, 2019. pp. 96-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{8a31fae7e31a4e1693f3556b2f31be71,
title = "Bounded Reducibility for Computable Numberings",
abstract = "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.",
author = "Nikolay Bazhenov and Manat Mustafa and Sergei Ospichev",
year = "2019",
month = jan,
day = "1",
doi = "10.1007/978-3-030-22996-2_9",
language = "English",
isbn = "9783030229955",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "96--107",
editor = "Florin Manea and Barnaby Martin and Dani{\"e}l Paulusma and Giuseppe Primiero",
booktitle = "Computing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings",
address = "United States",
note = "15th Conference on Computability in Europe, CiE 2019 ; Conference date: 15-07-2019 Through 19-07-2019",
}
RIS
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
T2 - 15th Conference on Computability in Europe, CiE 2019
Y2 - 15 July 2019 through 19 July 2019
ER -
