Turing computable embeddings, computable infinitary equivalence, and linear orders

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

1 Цитирования (Scopus)

Аннотация

We study Turing computable embeddings for various classes of linear orders. The concept of a Turing computable embedding (or tc-embedding for short) was developed by Calvert, Cummins, Knight, and Miller as an effective counterpart for Borel embeddings. We are focused on tc-embeddings for classes equipped with computable infinitary Σα equivalence, denoted by ∼c α. In this paper, we isolate a natural subclass of linear orders, denoted by WMB, such that (WMB, ≅) is not universal under tc-embeddings, but for any computable ordinal α ≥ 5, (WMB, ∼c α) is universal under tc-embeddings. Informally speaking, WMB is not tc-universal, but it becomes tc-universal if one imposes some natural restrictions on the effective complexity of the syntax. We also give a complete syntactic characterization for classes (K, ≅) that are Turing computably embeddable into some specific classes (C, ≅) of well-orders. This extends the similar result of Knight, Miller, and Vanden Boom for the class of all finite linear orders Cfin.

Язык оригиналаанглийский
Название основной публикацииUnveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings
РедакторыJ Kari, F Manea, Petre
ИздательSpringer-Verlag GmbH and Co. KG
Страницы141-151
Число страниц11
Том10307 LNCS
ISBN (печатное издание)9783319587400
DOI
СостояниеОпубликовано - 1 янв 2017
Событие13th Conference on Computability in Europe, CiE 2017 - Turku, Финляндия
Продолжительность: 12 июн 201716 июн 2017

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

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

Конференция

Конференция13th Conference on Computability in Europe, CiE 2017
СтранаФинляндия
ГородTurku
Период12.06.201716.06.2017

Fingerprint Подробные сведения о темах исследования «Turing computable embeddings, computable infinitary equivalence, and linear orders». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Bazhenov, N. (2017). Turing computable embeddings, computable infinitary equivalence, and linear orders. В J. Kari, F. Manea, & Petre (Ред.), Unveiling Dynamics and Complexity - 13th Conference on Computability in Europe, CiE 2017, Proceedings (Том 10307 LNCS, стр. 141-151). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10307 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-58741-7_15