Computable isomorphisms of distributive lattices

Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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
EditorsT. V. Gopal, Junzo Watada
PublisherSpringer Verlag
Pages28-41
Number of pages14
ISBN (Print)9783030148119
DOIs
Publication statusPublished - Jan 1 2019
Event15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 - Kitakyushu, Japan
Duration: Apr 13 2019Apr 16 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

Conference

Conference15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
CountryJapan
CityKitakyushu
Period4/13/194/16/19

Fingerprint

Distributive Lattice
Reducibility
Equivalence relation
Algebra
Isomorphism
Computable Structure
Heyting Algebra
Computability
Undirected Graph
Metric space
Hierarchy
Standards

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Bazhenov, N., Mustafa, M., & Yamaleev, M. (2019). Computable isomorphisms of distributive lattices. In T. V. Gopal, & J. Watada (Eds.), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings (pp. 28-41). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-030-14812-6_3

Computable isomorphisms of distributive lattices. / Bazhenov, Nikolay; Mustafa, Manat; Yamaleev, Mars.

Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. ed. / T. V. Gopal; Junzo Watada. Springer Verlag, 2019. p. 28-41 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11436 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bazhenov, N, Mustafa, M & Yamaleev, M 2019, Computable isomorphisms of distributive lattices. in TV Gopal & J Watada (eds), Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11436 LNCS, Springer Verlag, pp. 28-41, 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019, Kitakyushu, Japan, 4/13/19. https://doi.org/10.1007/978-3-030-14812-6_3
Bazhenov N, Mustafa M, Yamaleev M. Computable isomorphisms of distributive lattices. In Gopal TV, Watada J, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Springer Verlag. 2019. p. 28-41. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-030-14812-6_3
Bazhenov, Nikolay ; Mustafa, Manat ; Yamaleev, Mars. / Computable isomorphisms of distributive lattices. Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. editor / T. V. Gopal ; Junzo Watada. Springer Verlag, 2019. pp. 28-41 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{83bb3cea099f453cae9162ab6ecdd8a2,
title = "Computable isomorphisms of distributive lattices",
abstract = "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.",
keywords = "Computable categoricity, Computable metric space, Computable reducibility, Distributive lattice, Equivalence relation, Heyting algebra",
author = "Nikolay Bazhenov and Manat Mustafa and Mars Yamaleev",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/978-3-030-14812-6_3",
language = "English",
isbn = "9783030148119",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "28--41",
editor = "Gopal, {T. V.} and Junzo Watada",
booktitle = "Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings",
address = "Germany",

}

TY - GEN

T1 - Computable isomorphisms of distributive lattices

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Yamaleev, Mars

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - Computable categoricity

KW - Computable metric space

KW - Computable reducibility

KW - Distributive lattice

KW - Equivalence relation

KW - Heyting algebra

UR - http://www.scopus.com/inward/record.url?scp=85064865052&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85064865052&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-14812-6_3

DO - 10.1007/978-3-030-14812-6_3

M3 - Conference contribution

SN - 9783030148119

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 28

EP - 41

BT - Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings

A2 - Gopal, T. V.

A2 - Watada, Junzo

PB - Springer Verlag

ER -