Sergei Ospichev

dblp:244/0581 · also Sergey Ospichev · DBLP profile ↗
← Back
3ranked-venue papers
0as first author
1since 2021 · last 2022
0000-0001-9912-6364ORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 3 · 1 since 2021
YearPublicationVenuePosition
2022 Rogers semilattices of punctual numberings
abstract
Abstract The paper works within the framework of punctual computability, which is focused on eliminating unbounded search from constructions in algebra and infinite combinatorics. We study punctual numberings, that is, uniform computations for families S of primitive recursive functions. The punctual reducibility between numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We show that any infinite, uniformly primitive recursive family S induces an infinite Rogers pr-semilattice R. We prove that the semilattice R does not have minimal elements, and every nontrivial interval inside R contains an infinite antichain. In addition, every non-greatest element from R is a part of an infinite antichain. We show that the $\Sigma_1$ -fragment of the theory Th(R) is decidable.
Nikolay Bazhenov 0001, Manat Mustafa, Sergei Ospichev
Math. Struct. Comput. Sci.3
2020 Semilattices of Punctual Numberings
Nikolay Bazhenov 0001, Manat Mustafa, Sergei Ospichev
TAMC3
2019 Bounded Reducibility for Computable Numberings
Nikolay Bazhenov 0001, Manat Mustafa, Sergei Ospichev
CiE3