Computable isomorphisms of distributive lattices

Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev

Research output: Chapter in Book/Report/Conference proceedingConference contributionResearchpeer-review

1 Citation (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.

Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings
EditorsJunzo Watada, T. V. Gopal
PublisherSpringer-Verlag GmbH and Co. KG
Number of pages14
ISBN (Print)9783030148119
Publication statusPublished - 1 Jan 2019
Event15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan
Duration: 13 Apr 201916 Apr 2019

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11436 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019


  • Computable categoricity
  • Computable metric space
  • Computable reducibility
  • Distributive lattice
  • Equivalence relation
  • Heyting algebra

Fingerprint Dive into the research topics of 'Computable isomorphisms of distributive lattices'. Together they form a unique fingerprint.

Cite this