Degrees of categoricity for prime and homogeneous models

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

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

Аннотация

We study effective categoricity for homogeneous and prime models of a complete theory. For a computable structure S, the degree of categoricity of S is the least Turing degree which can compute isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for homogeneous models and for prime Heyting algebras, i.e. prime models of a complete extension of the theory of Heyting algebras. We show that 0(ω+1) is the degree of categoricity for a homogeneous model. We prove that any Turing degree which is d.c.e. in and above 0(n), where 3 ≤ n < ω, is the degree of categoricity for a prime Heyting algebra.

Язык оригиналаанглийский
Название основной публикацииSailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
РедакторыF Manea, RG Miller, D Nowotka
ИздательSpringer-Verlag GmbH and Co. KG
Страницы40-49
Число страниц10
ISBN (печатное издание)9783319944173
DOI
СостояниеОпубликовано - 1 янв 2018
Событие14th Conference on Computability in Europe, CiE 2018 - Kiel, Германия
Продолжительность: 30 июл 20183 авг 2018

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

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

Конференция

Конференция14th Conference on Computability in Europe, CiE 2018
СтранаГермания
ГородKiel
Период30.07.201803.08.2018

Fingerprint Подробные сведения о темах исследования «Degrees of categoricity for prime and homogeneous models». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Bazhenov, N., & Marchuk, M. (2018). Degrees of categoricity for prime and homogeneous models. В F. Manea, RG. Miller, & D. Nowotka (Ред.), Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings (стр. 40-49). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10936 LNCS). Springer-Verlag GmbH and Co. KG. https://doi.org/10.1007/978-3-319-94418-0_4