Semilattices of Punctual Numberings

Результат исследования: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

Аннотация

The theory of numberings studies uniform computations for classes of mathematical objects. A large body of literature is devoted to investigations of computable numberings, i.e. uniform enumerations for families of computably enumerable sets, and the reducibility among these numberings. This reducibility, induced by Turing computable functions, aims to classify the algorithmic complexity of numberings. The paper is inspired by the recent advances in the area of punctual algebraic structures. We recast the classical studies of numberings in the punctual setting—we study punctual numberings, i.e. uniform computations for families of primitive recursive functions. The reducibility between punctual numberings is induced by primitive recursive functions. This approach gives rise to upper semilattices of degrees, which are called Rogers pr-semilattices. We prove that any infinite Rogers pr-semilattice is dense and does not have minimal elements. Furthermore, we give an example of infinite Rogers pr-semilattice, which is a lattice. These results exhibit interesting phenomena, which do not occur in the classical case of computable numberings and their semilattices.

Язык оригиналаанглийский
Название основной публикацииTheory and Applications of Models of Computation - 16th International Conference, TAMC 2020, Proceedings
РедакторыJianer Chen, Qilong Feng, Jinhui Xu
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы1-12
Число страниц12
ISBN (печатное издание)9783030592660
DOI
СостояниеОпубликовано - 2020
Событие16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020 - Changsha, Китай
Продолжительность: 18 окт 202020 окт 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12337 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция16th Annual Conference on Theory and Applications of Models of Computation, TAMC 2020
СтранаКитай
ГородChangsha
Период18.10.202020.10.2020

Fingerprint Подробные сведения о темах исследования «Semilattices of Punctual Numberings». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать