Switch to: References

Add citations

You must login to add citations.
  1. Π₁¹ Relations and Paths Through ᵊ.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585 - 611.
  • On the Complexity of the Successivity Relation in Computable Linear Orderings.Rod Downey, Steffen Lempp & Guohua Wu - 2010 - Journal of Mathematical Logic 10 (1):83-99.
    In this paper, we solve a long-standing open question, about the spectrum of the successivity relation on a computable linear ordering. We show that if a computable linear ordering [Formula: see text] has infinitely many successivities, then the spectrum of the successivity relation is closed upwards in the computably enumerable Turing degrees. To do this, we use a new method of constructing [Formula: see text]-isomorphisms, which has already found other applications such as Downey, Kastermans and Lempp [9] and is of (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Degree Spectra of Relations on Computable Structures in the Presence of Δ02 Isomorphisms.Denis R. Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697 - 720.
    We give some new examples of possible degree spectra of invariant relations on Δ 0 2 -categorical computable structures, which demonstrate that such spectra can be fairly complicated. On the other hand, we show that there are nontrivial restrictions on the sets of degrees that can be realized as degree spectra of such relations. In particular, we give a sufficient condition for a relation to have infinite degree spectrum that implies that every invariant computable relation on a Δ 0 2 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations.John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey - 2007 - Journal of Symbolic Logic 72 (3):1003 - 1018.
    We study the weak truth-table and truth-table degrees of the images of subsets of computable structures under isomorphisms between computable structures. In particular, we show that there is a low c.e. set that is not weak truth-table reducible to any initial segment of any scattered computable linear ordering. Countable $\Pi _{1}^{0}$ subsets of 2ω and Kolmogorov complexity play a major role in the proof.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Computability-Theoretic Complexity of Countable Structures.Valentina S. Harizanov - 2002 - Bulletin of Symbolic Logic 8 (4):457-477.
  • Degree Spectra of Relations on Computable Structures in the Presence of Δ20 Isomorphisms.Denis Hirschfeldt - 2002 - Journal of Symbolic Logic 67 (2):697-720.
  • Generalized Weak Presentations.Alexandra Shlapentokh - 2002 - Journal of Symbolic Logic 67 (2):787-819.
    Let K be a computable field. Let F be a collection of recursive functions over K, possibly including field operations. We investigate the following question. Given an r.e. degree a, is there an injective map j: K $\longrightarrow \mathbb{N}$ such that j(K) is of degree a and all the functions in F are translated by restrictions of total recursive functions.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark  
  • Π 1 1 Relations and Paths Through.Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore - 2004 - Journal of Symbolic Logic 69 (2):585-611.
  • Coding a Family of Sets.J. F. Knight - 1998 - Annals of Pure and Applied Logic 94 (1-3):127-142.
    In this paper, we state a metatheorem for constructions involving coding. Using the metatheorem, we obtain results on coding a family of sets into a family of relations, or into a single relation. For a concrete example, we show that the set of limit points in a recursive ordering of type ω 2 can have arbitrary 2-REA degree.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Possible Degrees in Recursive Copies.C. J. Ash & J. F. Knight - 1995 - Annals of Pure and Applied Logic 75 (3):215-221.
    Let be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this is not the case. Here (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  • Quasi-Simple Relations in Copies of a Given Recursive Structure.C. J. Ash, J. F. Knight & J. B. Remmel - 1997 - Annals of Pure and Applied Logic 86 (3):203-218.
  • The Possible Turing Degree of the Nonzero Member in a Two Element Degree Spectrum.Valentina S. Harizanov - 1993 - Annals of Pure and Applied Logic 60 (1):1-30.
    We construct a recursive model , a recursive subset R of its domain, and a Turing degree x 0 satisfying the following condition. The nonrecursive images of R under all isomorphisms from to other recursive models are of Turing degree x and cannot be recursively enumerable.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Possible Degrees in Recursive Copies II.C. J. Ash & J. F. Knight - 1997 - Annals of Pure and Applied Logic 87 (2):151-165.
    We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions on a pair (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  • Permitting, Forcing, and Copying of a Given Recursive Relation.C. J. Ash, P. Cholak & J. F. Knight - 1997 - Annals of Pure and Applied Logic 86 (3):219-236.
  • Turing Degrees of Certain Isomorphic Images of Computable Relations.Valentina S. Harizanov - 1998 - Annals of Pure and Applied Logic 93 (1-3):103-113.
    A model is computable if its domain is a computable set and its relations and functions are uniformly computable. Let be a computable model and let R be an extra relation on the domain of . That is, R is not named in the language of . We define to be the set of Turing degrees of the images f under all isomorphisms f from to computable models. We investigate conditions on and R which are sufficient and necessary for to (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  • Computable Isomorphisms, Degree Spectra of Relations, and Scott Families.Bakhadyr Khoussainov & Richard A. Shore - 1998 - Annals of Pure and Applied Logic 93 (1-3):153-193.
    The spectrum of a relation on a computable structure is the set of Turing degrees of the image of R under all isomorphisms between and any other computable structure . The relation is intrinsically computably enumerable if its image under all such isomorphisms is c.e. We prove that any computable partially ordered set is isomorphic to the spectrum of an intrinsically c.e. relation on a computable structure. Moreover, the isomorphism can be constructed in such a way that the image of (...)
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   15 citations  
  • Turing Degrees of Hypersimple Relations on Computable Structures.Valentina S. Harizanov - 2003 - Annals of Pure and Applied Logic 121 (2-3):209-226.
    Let be an infinite computable structure, and let R be an additional computable relation on its domain A. The syntactic notion of formal hypersimplicity of R on , first introduced and studied by Hird, is analogous to the computability-theoretic notion of hypersimplicity of R on A, given the definability of certain effective sequences of relations on A. Assuming that R is formally hypersimple on , we give general sufficient conditions for the existence of a computable isomorphic copy of on whose (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  • Degree Spectra of the Successor Relation of Computable Linear Orderings.Jennifer Chubb, Andrey Frolov & Valentina Harizanov - 2009 - Archive for Mathematical Logic 48 (1):7-13.
    We establish that for every computably enumerable (c.e.) Turing degree b the upper cone of c.e. Turing degrees determined by b is the degree spectrum of the successor relation of some computable linear ordering. This follows from our main result, that for a large class of linear orderings the degree spectrum of the successor relation is closed upward in the c.e. Turing degrees.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  • Degrees of Categoricity on a Cone Via Η-Systems.Barbara F. Csima & Matthew Harrison-Trainor - 2017 - Journal of Symbolic Logic 82 (1):325-346.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  • 1995 European Summer Meeting of the Association for Symbolic Logic.Johann A. Makowsky - 1997 - Bulletin of Symbolic Logic 3 (1):73-147.
  • Degree Spectra of Relations on Computable Structures.Denis R. Hirschfeldt - 2000 - Bulletin of Symbolic Logic 6 (2):197-212.