22 found
Sort by:
  1. Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán (2011). Computability of Fraïssé Limits. Journal of Symbolic Logic 76 (1):66 - 93.
    Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  2. Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, Valentina S. Harizanov & Amir A. Togha (2010). Spaces of Orders and Their Turing Degree Spectra. Annals of Pure and Applied Logic 161 (9):1134-1143.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov (2009). Effective Categoricity of Abelian P-Groups. Annals of Pure and Applied Logic 159 (1):187-197.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn (2009). Intrinsic Bounds on Complexity and Definability at Limit Levels. Journal of Symbolic Logic 74 (3):1047-1060.
    We show that for every computable limit ordinal α, there is a computable structure A that is $\Delta _\alpha ^0 $ categorical, but not relatively $\Delta _\alpha ^0 $ categorical (equivalently. it does not have a formally $\Sigma _\alpha ^0 $ Scott family). We also show that for every computable limit ordinal a, there is a computable structure A with an additional relation R that is intrinsically $\Sigma _\alpha ^0 $ on A. but not relatively intrinsically $\Sigma _\alpha ^0 $ (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Valentina S. Harizanov, Carl G. Jockusch Jr & Julia F. Knight (2009). Chains and Antichains in Partial Orderings. Archive for Mathematical Logic 48 (1):39-53.
    We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is ${\Sigma _{1}^{1}}$ or ${\Pi _{1}^{1}}$ , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two ${\Pi _{1}^{1}}$ sets. Our main result is that there (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Jennifer Chubb, Valentina S. Harizanov, Andrei S. Morozov, Sarah Pingrey & Eric Ufferman (2008). Partial Automorphism Semigroups. Annals of Pure and Applied Logic 156 (2):245-258.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  7. John Chisholm, Jennifer Chubb, Valentina S. Harizanov, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl & Sarah Pingrey (2007). $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  8. Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare (2007). Bounding Homogeneous Models. Journal of Symbolic Logic 72 (1):305 - 323.
    A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  9. Valentina S. Harizanov & Russel G. Miller (2007). Spectra of Structures and Relations. Journal of Symbolic Logic 72 (1):324 - 348.
    We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally universal. We use our results (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Rumen D. Dimitrov, Valentina S. Harizanov & Andrei S. Morozov (2005). Dependence Relations in Computably Rigid Computable Vector Spaces. Annals of Pure and Applied Logic 132 (1):97-108.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore (2004). Π11 Relations and Paths Through. Journal of Symbolic Logic 69 (2):585-611.
    Direct download  
     
    My bibliography  
     
    Export citation  
  12. Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Richard A. Shore (2004). Π 1 1 Relations and Paths Through. Journal of Symbolic Logic 69 (2):585-611.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Sergei S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Charles F. D. McCoy (2003). Simple and Immune Relations on Countable Structures. Archive for Mathematical Logic 42 (3):279-291.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Valentina S. Harizanov (2003). Turing Degrees of Hypersimple Relations on Computable Structures. Annals of Pure and Applied Logic 121 (2-3):209-226.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Valentina S. Harizanov (2002). Computability-Theoretic Complexity of Countable Structures. Bulletin of Symbolic Logic 8 (4):457-477.
  16. Valentina S. Harizanov, Julia F. Knight & Andrei S. Morozov (2002). Sequences of N-Diagrams. Journal of Symbolic Logic 67 (3):1227-1247.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  17. Valentina S. Harizanov (1998). Turing Degrees of Certain Isomorphic Images of Computable Relations. Annals of Pure and Applied Logic 93 (1-3):103-113.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Valentina S. Harizanov (1996). Effectively and Noneffectively Nowhere Simple Sets. Mathematical Logic Quarterly 42 (1):241-248.
    No categories
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  19. Valentina S. Harizanov (1993). The Possible Turing Degree of the Nonzero Member in a Two Element Degree Spectrum. Annals of Pure and Applied Logic 60 (1):1-30.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Valentina S. Harizanov (1991). Some Effects of Ash–Nerode and Other Decidability Conditions on Degree Spectra. Annals of Pure and Applied Logic 55 (1):51-65.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. Valentina S. Harizanov (1991). Uncountable Degree Spectra. Annals of Pure and Applied Logic 54 (3):255-263.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation