Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Degrees of categoricity for prime and homogeneous models. / Bazhenov, Nikolay; Marchuk, Margarita.
Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings. ред. / F Manea; RG Miller; D Nowotka. Springer-Verlag GmbH and Co. KG, 2018. стр. 40-49 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 10936 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Degrees of categoricity for prime and homogeneous models
AU - Bazhenov, Nikolay
AU - Marchuk, Margarita
PY - 2018/1/1
Y1 - 2018/1/1
N2 - We study effective categoricity for homogeneous and prime models of a complete theory. For a computable structure S, the degree of categoricity of S is the least Turing degree which can compute isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for homogeneous models and for prime Heyting algebras, i.e. prime models of a complete extension of the theory of Heyting algebras. We show that 0(ω+1) is the degree of categoricity for a homogeneous model. We prove that any Turing degree which is d.c.e. in and above 0(n), where 3 ≤ n < ω, is the degree of categoricity for a prime Heyting algebra.
AB - We study effective categoricity for homogeneous and prime models of a complete theory. For a computable structure S, the degree of categoricity of S is the least Turing degree which can compute isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for homogeneous models and for prime Heyting algebras, i.e. prime models of a complete extension of the theory of Heyting algebras. We show that 0(ω+1) is the degree of categoricity for a homogeneous model. We prove that any Turing degree which is d.c.e. in and above 0(n), where 3 ≤ n < ω, is the degree of categoricity for a prime Heyting algebra.
KW - Autostability spectrum
KW - Categoricity spectrum
KW - Computable categoricity
KW - Computable structure
KW - Degree of categoricity
KW - Heyting algebra
KW - Homogeneous model
KW - Prime model
KW - COMPUTABLE CATEGORICITY
KW - SPECTRA
KW - AUTOSTABILITY
UR - http://www.scopus.com/inward/record.url?scp=85051140001&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-94418-0_4
DO - 10.1007/978-3-319-94418-0_4
M3 - Conference contribution
AN - SCOPUS:85051140001
SN - 9783319944173
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 40
EP - 49
BT - Sailing Routes in the World of Computation - 14th Conference on Computability in Europe, CiE 2018, Proceedings
A2 - Manea, F
A2 - Miller, RG
A2 - Nowotka, D
PB - Springer-Verlag GmbH and Co. KG
T2 - 14th Conference on Computability in Europe, CiE 2018
Y2 - 30 July 2018 through 3 August 2018
ER -
ID: 16113225