Computable isomorphisms of distributive lattices

Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev

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

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

Аннотация

A standard tool for the classifying computability-theoretic complexity of equivalence relations is provided by computable reducibility. This gives rise to a rich degree-structure which has been extensively studied in the literature. In this paper, we show that equivalence relations, which are complete for computable reducibility in various levels of the hyperarithmetical hierarchy, arise in a natural way in computable structure theory. We prove that for any computable successor ordinal α, the relation of (formula presented) isomorphism for computable distributive lattices is (formula presented) complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

Язык оригиналаанглийский
Название основной публикацииTheory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
РедакторыJunzo Watada, T. V. Gopal
ИздательSpringer-Verlag GmbH and Co. KG
Страницы28-41
Число страниц14
ISBN (печатное издание)9783030148119
DOI
СостояниеОпубликовано - 1 янв 2019
Событие15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Япония
Продолжительность: 13 апр 201916 апр 2019

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

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

Конференция

Конференция15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
СтранаЯпония
ГородKitakyushu
Период13.04.201916.04.2019

Fingerprint Подробные сведения о темах исследования «Computable isomorphisms of distributive lattices». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать