A Note on Computable Embeddings for Ordinals and Their Reverses

Nikolay Bazhenov, Stefan Vatev

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

Аннотация

We continue the study of computable embeddings for pairs of structures, i.e. for classes containing precisely two non-isomorphic structures. Surprisingly, even for some pairs of simple linear orders, computable embeddings induce a non-trivial degree structure. Our main result shows that although is computably embeddable in, the class is not computably embeddable in for any natural number.

Язык оригиналаанглийский
Название основной публикацииBeyond the Horizon of Computability - 16th Conference on Computability in Europe, CiE 2020, Proceedings
РедакторыMarcella Anselmo, Gianluca Della Vedova, Florin Manea, Arno Pauly
ИздательSpringer Gabler
Страницы1-13
Число страниц13
ISBN (печатное издание)9783030514655
DOI
СостояниеОпубликовано - 1 июл 2020
Событие16th Conference on Computability in Europe, CiE 2020 - Fisciano, Италия
Продолжительность: 29 июн 20203 июл 2020

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

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

Конференция

Конференция16th Conference on Computability in Europe, CiE 2020
СтранаИталия
ГородFisciano
Период29.06.202003.07.2020

Fingerprint Подробные сведения о темах исследования «A Note on Computable Embeddings for Ordinals and Their Reverses». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать