A note on effective categoricity for linear orderings

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

Аннотация

We study effective categoricity for linear orderings. For a computable structure S, the degree of categoricity of S is the least Turing degree which is capable of computing isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for linear orderings. We show that for an infinite computable ordinal α, every Turing degree c.e. in and above 0(2α+2) is the degree of categoricity for some linear ordering. We obtain similar results for linearly ordered abelian groups and decidable linear orderings.

Язык оригиналаанглийский
Название основной публикацииTheory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
РедакторыTV Gopal, G Jager, S Steila
ИздательSpringer-Verlag GmbH and Co. KG
Страницы85-96
Число страниц12
ISBN (печатное издание)9783319559100
DOI
СостояниеОпубликовано - 1 янв 2017
Событие14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017 - Bern, Швейцария
Продолжительность: 20 апр 201722 апр 2017

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

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

Конференция

Конференция14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
СтранаШвейцария
ГородBern
Период20.04.201722.04.2017

Fingerprint Подробные сведения о темах исследования «A note on effective categoricity for linear orderings». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать