Rogers semilattices of punctual numberings | Sciact - Система учета научной деятельности ИМ СО РАН

Rogers semilattices of punctual numberings Научная публикация

Журнал

Mathematical Structures in Computer Science
ISSN: 0960-1295 , E-ISSN: 1469-8072

Вых. Данные

Год: 2022, Том: 32, Номер: 2, Страницы: 164-188 Страниц : 25 DOI: 10.1017/S0960129522000093

Ключевые слова

decidability; Friedberg numbering; online computation; primitive recursion; punctual structure; Rogers semilattice; Theory of numberings; upper semilattice

Авторы

Bazhenov N. ¹ , Mustafa M. ² , Ospichev S. ¹

Организации

1	Sobolev Institute of Mathematics, 4 Acad. Koptyug Avenue, Novosibirsk, 630090, Russian Federation
2	Department of Mathematics, School of Sciences and Humanities, Nazarbayev University, 53 Qabanbay Batyr Avenue, Nur-Sultan, 010000, Kazakhstan

Информация о финансировании (1)

Министерство науки и высшего образования РФ
Математический центр в Академгородке

075-15-2019-1613, 075-15-2022-281

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 Σ1 -fragment of the theory Th(R) is decidable.

Bazhenov N. , Mustafa M. , Ospichev S.
Rogers semilattices of punctual numberings
Mathematical Structures in Computer Science. 2022. V.32. N2. P.164-188. DOI: 10.1017/S0960129522000093 WOS Scopus РИНЦ OpenAlex

Web of science:	WOS:000774642000001
Scopus:	2-s2.0-85128149845
РИНЦ:	48428493
OpenAlex:	W4220772554

БД	Цитирований
Scopus	3
Web of science	3
OpenAlex	3
РИНЦ	3