Standard
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. / Junzo Watada; T. V. Gopal. Springer-Verlag GmbH and Co. KG, 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 proceeding › Conference contribution › Research › peer-review
Harvard
Bazhenov, N, Mustafa, M & Yamaleev, M 2019,
Computable isomorphisms of distributive lattices. in J Watada & TV Gopal (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 GmbH and Co. KG, pp. 28-41, 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019, Kitakyushu, Japan,
13.04.2019.
https://doi.org/10.1007/978-3-030-14812-6_3
APA
Vancouver
Bazhenov N, Mustafa M, Yamaleev M.
Computable isomorphisms of distributive lattices. In Watada J, Gopal TV, editors, Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings. Springer-Verlag GmbH and Co. KG. 2019. p. 28-41. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-14812-6_3
Author
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 / Junzo Watada ; T. V. Gopal. Springer-Verlag GmbH and Co. KG, 2019. pp. 28-41 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
BibTeX
@inproceedings{335c92defbfa4117b014ac2677733afb,
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",
note = "Publisher Copyright: {\textcopyright} Springer Nature Switzerland AG 2019.; 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019 ; Conference date: 13-04-2019 Through 16-04-2019",
year = "2019",
month = jan,
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 GmbH and Co. KG",
pages = "28--41",
editor = "Junzo Watada and Gopal, {T. V.}",
booktitle = "Theory and Applications of Models of Computation - 15th Annual Conference, TAMC 2019, Proceedings",
address = "Germany",
}
RIS
TY - GEN
T1 - Computable isomorphisms of distributive lattices
AU - Bazhenov, Nikolay
AU - Mustafa, Manat
AU - Yamaleev, Mars
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
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
U2 - 10.1007/978-3-030-14812-6_3
DO - 10.1007/978-3-030-14812-6_3
M3 - Conference contribution
AN - SCOPUS:85064865052
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 - Watada, Junzo
A2 - Gopal, T. V.
PB - Springer-Verlag GmbH and Co. KG
T2 - 15th Annual Conference on Theory and Applications of Models of Computation, TAMC 2019
Y2 - 13 April 2019 through 16 April 2019
ER -
