Abstract
| 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 |
Fingerprint
Cite this
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
}
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 -