Standard

Computability of Distributive Lattices. / Bazhenov, N. A.; Frolov, A. N.; Kalimullin, I. Sh et al.

In: Siberian Mathematical Journal, Vol. 58, No. 6, 01.11.2017, p. 959-970.

Research output: Contribution to journal › Article › peer-review

Harvard

Bazhenov, NA, Frolov, AN, Kalimullin, IS & Melnikov, AG 2017, 'Computability of Distributive Lattices', Siberian Mathematical Journal, vol. 58, no. 6, pp. 959-970. https://doi.org/10.1134/S0037446617060052

APA

Bazhenov, N. A., Frolov, A. N., Kalimullin, I. S., & Melnikov, A. G. (2017). Computability of Distributive Lattices. Siberian Mathematical Journal, 58(6), 959-970. https://doi.org/10.1134/S0037446617060052

Vancouver

Bazhenov NA, Frolov AN, Kalimullin IS, Melnikov AG. Computability of Distributive Lattices. Siberian Mathematical Journal. 2017 Nov 1;58(6):959-970. doi: 10.1134/S0037446617060052

Author

Bazhenov, N. A. ; Frolov, A. N. ; Kalimullin, I. Sh et al. / Computability of Distributive Lattices. In: Siberian Mathematical Journal. 2017 ; Vol. 58, No. 6. pp. 959-970.

BibTeX

@article{9d138803655741ac947212fcd9e1b20f,
title = "Computability of Distributive Lattices",
abstract = "The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum {d: d ≠ 0}. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively Δ2 0-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.",
keywords = "computable categoricity, computable structure, degree spectrum, distributive lattice, EFFECTIVE CATEGORICITY, DEGREE SPECTRA",
author = "Bazhenov, {N. A.} and Frolov, {A. N.} and Kalimullin, {I. Sh} and Melnikov, {A. G.}",
year = "2017",
month = nov,
day = "1",
doi = "10.1134/S0037446617060052",
language = "English",
volume = "58",
pages = "959--970",
journal = "Siberian Mathematical Journal",
issn = "0037-4466",
publisher = "MAIK NAUKA/INTERPERIODICA/SPRINGER",
number = "6",

}

RIS

TY - JOUR

T1 - Computability of Distributive Lattices

AU - Bazhenov, N. A.

AU - Frolov, A. N.

AU - Kalimullin, I. Sh

AU - Melnikov, A. G.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum {d: d ≠ 0}. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively Δ2 0-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.

AB - The class of (not necessarily distributive) countable lattices is HKSS-universal, and it is also known that the class of countable linear orders is not universal with respect to degree spectra neither to computable categoricity. We investigate the intermediate class of distributive lattices and construct a distributive lattice with degree spectrum {d: d ≠ 0}. It is not known whether a linear order with this property exists. We show that there is a computably categorical distributive lattice that is not relatively Δ2 0-categorical. It is well known that no linear order can have this property. The question of the universality of countable distributive lattices remains open.

KW - computable categoricity

KW - computable structure

KW - degree spectrum

KW - distributive lattice

KW - EFFECTIVE CATEGORICITY

KW - DEGREE SPECTRA

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

U2 - 10.1134/S0037446617060052

DO - 10.1134/S0037446617060052

M3 - Article

AN - SCOPUS:85042141013

VL - 58

SP - 959

EP - 970

JO - Siberian Mathematical Journal

JF - Siberian Mathematical Journal

SN - 0037-4466

IS - 6

ER -

ID: 9954152