Well-Orders Realized by C.E. Equivalence Relations

Nikolay Bazhenov, Maxim Zubkov

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

Аннотация

We study countable linear orders realized by computably enumerable equivalence relations (ceers). A ceer E realizes a linear order L if there exists a computably enumerable binary relation ⊴ respecting E such that the induced quotient structure (N/ E, ⊴ ) is isomorphic to L. In this line of research, there are many nontrivial results demonstrating complex interplay between the computability-theoretic properties of a ceer E and the isomorphism types of orders L realizable by E. For example, Gavryushkin, Khoussainov, and Stephan proved that there is a ceer E realizing only one order type—the type of ω+ 1 + ω. In this paper, we obtain a complete characterization of well-orders L realizable by a given ceer E for the case when E realizes some ordinal α< ω3. Informally speaking, our proofs develop methods of fine-tuning the behavior of limit points of L via computability-theoretic properties of E.

Язык оригиналаанглийский
Название основной публикацииRevolutions and Revelations in Computability - 18th Conference on Computability in Europe, CiE 2022, Proceedings
РедакторыUlrich Berger, Arno Pauly, Johanna N.Y. Franklin, Florin Manea
ИздательSpringer Science and Business Media Deutschland GmbH
Страницы13-23
Число страниц11
ISBN (печатное издание)9783031087394
DOI
СостояниеОпубликовано - 2022
Событие18th Conference on Computability in Europe, CiE 2022 - Swansea, Великобритания
Продолжительность: 11 июл 202215 июл 2022

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

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

Конференция

Конференция18th Conference on Computability in Europe, CiE 2022
СтранаВеликобритания
ГородSwansea
Период11.07.202215.07.2022

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «Well-Orders Realized by C.E. Equivalence Relations». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать