Switch to: References

Citations of:

Finite computable dimension and degrees of categoricity

Barbara F. Csima & Jonathan Stephenson

Annals of Pure and Applied Logic 170 (1):58-94 (2019)

Add citations

You must login to add citations.

Degrees of bi-embeddable categoricity of equivalence structures.Nikolay Bazhenov, Ekaterina Fokina, Dino Rossegger & Luca San Mauro - 2019 - Archive for Mathematical Logic 58 (5-6):543-563.details We study the algorithmic complexity of embeddings between bi-embeddable equivalence structures. We define the notions of computable bi-embeddable categoricity, \ bi-embeddable categoricity, and degrees of bi-embeddable categoricity. These notions mirror the classical notions used to study the complexity of isomorphisms between structures. We show that the notions of \ bi-embeddable categoricity and relative \ bi-embeddable categoricity coincide for equivalence structures for \. We also prove that computable equivalence structures have degree of bi-embeddable categoricity \, or \. We furthermore obtain results (...) Download Export citation Bookmark 3 citations
Coding in the automorphism group of a computably categorical structure.Dan Turetsky - 2020 - Journal of Mathematical Logic 20 (3):2050016.details Using new techniques for controlling the categoricity spectrum of a structure, we construct a structure with degree of categoricity but infinite spectral dimension, answering a question of Bazhenov, Kalimullin and Yamaleev. Using the same techniques, we construct a computably categorical structure of non-computable Scott rank. Download Export citation Bookmark 3 citations
Degrees of categoricity and treeable degrees.Barbara F. Csima & Dino Rossegger - 2023 - Journal of Mathematical Logic 24 (3).details In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than 2 is (...) Download Export citation Bookmark
Every Δ20 degree is a strong degree of categoricity.Barbara F. Csima & Keng Meng Ng - 2022 - Journal of Mathematical Logic 22 (3).details A strong degree of categoricity is a Turing degree [Formula: see text] such that there is a computable structure [Formula: see text] that is [Formula: see text]-computably categorical (there is a [Formula: see text]-computable isomorphism between any two computable copies of [Formula: see text]), and such that there exist two computable copies of [Formula: see text] between which every isomorphism computes [Formula: see text]. The question of whether every [Formula: see text] degree is a strong degree of categoricity has been (...) Download Export citation Bookmark 1 citation

1