Bounded Reducibility for Computable Numberings

Nikolay Bazhenov, Manat Mustafa, Sergei Ospichev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish
Title of host publicationComputing with Foresight and Industry - 15th Conference on Computability in Europe, CiE 2019, Proceedings
EditorsFlorin Manea, Barnaby Martin, Daniël Paulusma, Giuseppe Primiero
PublisherSpringer Verlag
Pages96-107
Number of pages12
ISBN (Print)9783030229955
DOIs
Publication statusPublished - Jan 1 2019
Event15th Conference on Computability in Europe, CiE 2019 - Durham, United Kingdom
Duration: Jul 15 2019Jul 19 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11558 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference15th Conference on Computability in Europe, CiE 2019
CountryUnited Kingdom
CityDurham
Period7/15/197/19/19

Fingerprint

Reducibility
Semilattice
Algorithmic Complexity
Natural number
Family

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

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 Verlag. https://doi.org/10.1007/978-3-030-22996-2_9

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 Verlag, 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 proceedingConference contribution

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 Verlag, pp. 96-107, 15th Conference on Computability in Europe, CiE 2019, Durham, United Kingdom, 7/15/19. https://doi.org/10.1007/978-3-030-22996-2_9
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 Verlag. 2019. p. 96-107. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-22996-2_9
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 Verlag, 2019. pp. 96-107 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{5fd40c0d4e1f40ff87ace74c8043a7c9,
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 = "1",
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 Verlag",
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 = "Germany",

}

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

UR - http://www.scopus.com/inward/citedby.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

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

ER -