Computable Isomorphisms of Distributive Lattices

Nikolay Bazhenov; Manat Mustafa; Mars Yamaleev

Computable Isomorphisms of Distributive Lattices

Nikolay Bazhenov, Manat Mustafa, Mars Yamaleev

Department of Mathematics

Research output: Chapter in Book/Report/Conference proceeding › Chapter

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 Δ0α isomorphism for computable distributive lattices is Σ0α+2 complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

Original language	English
Title of host publication	Theory and Applications of Models of Computation
Subtitle of host publication	15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019, Proceedings
Editors	T V Gopal, Junzo Watada
Publisher	Springer International Publishing
Pages	28-41
Number of pages	14
Volume	11436
Edition	1
ISBN (Electronic)	978-3-030-14812-6
ISBN (Print)	978-3-030-14811-9
Publication status	Published - Mar 6 2019

Publication series

Name	Lecture Notes in Computer Science, vol 11436. Springer, Cham
Publisher	Springer

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, Kitakyushu, Japan, April 13–16, 2019, Proceedings (1 ed., Vol. 11436, pp. 28-41). (Lecture Notes in Computer Science, vol 11436. Springer, Cham). Springer International Publishing.

Computable Isomorphisms of Distributive Lattices. / Bazhenov, Nikolay; Mustafa, Manat; Yamaleev, Mars.

Theory and Applications of Models of Computation: 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019, Proceedings. ed. / T V Gopal; Junzo Watada. Vol. 11436 1. ed. Springer International Publishing, 2019. p. 28-41 (Lecture Notes in Computer Science, vol 11436. Springer, Cham).

Research output: Chapter in Book/Report/Conference proceeding › Chapter

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, Kitakyushu, Japan, April 13–16, 2019, Proceedings. 1 edn, vol. 11436, Lecture Notes in Computer Science, vol 11436. Springer, Cham, Springer International Publishing, pp. 28-41.

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, Kitakyushu, Japan, April 13–16, 2019, Proceedings. 1 ed. Vol. 11436. Springer International Publishing. 2019. p. 28-41. (Lecture Notes in Computer Science, vol 11436. Springer, Cham).

Bazhenov, Nikolay ; Mustafa, Manat ; Yamaleev, Mars. / Computable Isomorphisms of Distributive Lattices. Theory and Applications of Models of Computation: 15th Annual Conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019, Proceedings. editor / T V Gopal ; Junzo Watada. Vol. 11436 1. ed. Springer International Publishing, 2019. pp. 28-41 (Lecture Notes in Computer Science, vol 11436. Springer, Cham).

@inbook{2f37419e7d914611bb350ef95f238150,

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 Δ0α isomorphism for computable distributive lattices is Σ0α+2 complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.",

author = "Nikolay Bazhenov and Manat Mustafa and Mars Yamaleev",

year = "2019",

month = mar,

day = "6",

language = "English",

isbn = "978-3-030-14811-9",

volume = "11436",

series = "Lecture Notes in Computer Science, vol 11436. Springer, Cham",

publisher = "Springer International Publishing",

pages = "28--41",

editor = "Gopal, {T V } and Junzo Watada",

booktitle = "Theory and Applications of Models of Computation",

edition = "1",

}

TY - CHAP

T1 - Computable Isomorphisms of Distributive Lattices

AU - Bazhenov, Nikolay

AU - Mustafa, Manat

AU - Yamaleev, Mars

PY - 2019/3/6

Y1 - 2019/3/6

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 Δ0α isomorphism for computable distributive lattices is Σ0α+2 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 Δ0α isomorphism for computable distributive lattices is Σ0α+2 complete. We obtain similar results for Heyting algebras, undirected graphs, and uniformly discrete metric spaces.

M3 - Chapter

SN - 978-3-030-14811-9

VL - 11436

T3 - Lecture Notes in Computer Science, vol 11436. Springer, Cham

SP - 28

EP - 41

BT - Theory and Applications of Models of Computation

A2 - Gopal, T V

A2 - Watada, Junzo

PB - Springer International Publishing

ER -

Computable Isomorphisms of Distributive Lattices

Abstract

Publication series

Fingerprint

Cite this