TY - GEN
T1 - A note on effective categoricity for linear orderings
AU - Bazhenov, Nikolay
N1 - Publisher Copyright:
© Springer International Publishing AG 2017.
PY - 2017/1/1
Y1 - 2017/1/1
N2 - We study effective categoricity for linear orderings. For a computable structure S, the degree of categoricity of S is the least Turing degree which is capable of computing isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for linear orderings. We show that for an infinite computable ordinal α, every Turing degree c.e. in and above 0(2α+2) is the degree of categoricity for some linear ordering. We obtain similar results for linearly ordered abelian groups and decidable linear orderings.
AB - We study effective categoricity for linear orderings. For a computable structure S, the degree of categoricity of S is the least Turing degree which is capable of computing isomorphisms among arbitrary computable copies of S. We build new examples of degrees of categoricity for linear orderings. We show that for an infinite computable ordinal α, every Turing degree c.e. in and above 0(2α+2) is the degree of categoricity for some linear ordering. We obtain similar results for linearly ordered abelian groups and decidable linear orderings.
KW - Autostability relative to strong constructivizations
KW - Autostability spectrum
KW - Categoricity spectrum
KW - Computable categoricity
KW - Computable structure
KW - Decidable structure
KW - Degree of categoricity
KW - Linear ordering
KW - Ordered abelian group
KW - STABILITY
KW - COMPUTABLE CATEGORICITY
KW - RECURSIVE STRUCTURES
KW - COMPLEXITY
KW - MODEL-THEORY
KW - SPECTRA
UR - http://www.scopus.com/inward/record.url?scp=85018440589&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-55911-7_7
DO - 10.1007/978-3-319-55911-7_7
M3 - Conference contribution
AN - SCOPUS:85018440589
SN - 9783319559100
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 85
EP - 96
BT - Theory and Applications of Models of Computation - 14th Annual Conference, TAMC 2017, Proceedings
A2 - Gopal, TV
A2 - Jager, G
A2 - Steila, S
PB - Springer-Verlag GmbH and Co. KG
T2 - 14th Annual Conference on Theory and Applications of Models of Computation, TAMC 2017
Y2 - 20 April 2017 through 22 April 2017
ER -