38 found
Order:
Disambiguations
Valentina S. Harizanov [21]Valentina Harizanov [21]
See also
Valentina Harizanov
George Washington University
  1.  24
    Effective Categoricity of Equivalence Structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - Annals of Pure and Applied Logic 141 (1):61-78.
    We investigate effective categoricity of computable equivalence structures . We show that is computably categorical if and only if has only finitely many finite equivalence classes, or has only finitely many infinite classes, bounded character, and at most one finite k such that there are infinitely many classes of size k. We also prove that all computably categorical structures are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. Since all computable equivalence structures are relatively categorical, (...)
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   19 citations  
  2.  11
    Some Effects of Ash–Nerode and Other Decidability Conditions on Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 55 (1):51-65.
    With every new recursive relation R on a recursive model , we consider the images of R under all isomorphisms from to other recursive models. We call the set of Turing degrees of these images the degree spectrum of R on , and say that R is intrinsically r.e. if all the images are r.e. C. Ash and A. Nerode introduce an extra decidability condition on , expressed in terms of R. Assuming this decidability condition, they prove that R is (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  3.  39
    Isomorphism Relations on Computable Structures.Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles Mccoy & Antonio Montalbán - 2012 - Journal of Symbolic Logic 77 (1):122-132.
    We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  4.  31
    Enumerations in Computable Structure Theory.Sergey Goncharov, Valentina Harizanov, Julia Knight, Charles McCoy, Russell Miller & Reed Solomon - 2005 - Annals of Pure and Applied Logic 136 (3):219-246.
    We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  5.  25
    Π 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.
  6.  36
    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   9 citations  
  7.  12
    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   9 citations  
  8.  11
    Uncountable Degree Spectra.Valentina S. Harizanov - 1991 - Annals of Pure and Applied Logic 54 (3):255-263.
    We consider a recursive model and an additional recursive relation R on its domain, such that there are uncountably many different images of R under isomorphisms from to some recursive model isomorphic to . We study properties of the set of Turing degrees of all these isomorphic images of R on the domain of.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  9.  16
    Effective Categoricity of Abelian P -Groups.Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov - 2009 - Annals of Pure and Applied Logic 159 (1-2):187-197.
    We investigate effective categoricity of computable Abelian p-groups . We prove that all computably categorical Abelian p-groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p-groups are categorical and relatively categorical.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  10.  39
    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 (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  11.  29
    Computability-Theoretic Complexity of Countable Structures.Valentina S. Harizanov - 2002 - Bulletin of Symbolic Logic 8 (4):457-477.
  12.  80
    Simple and Immune Relations on Countable Structures.Sergei S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Charles F. D. McCoy - 2003 - Archive for Mathematical Logic 42 (3):279-291.
  13.  34
    Bounding Homogeneous Models.Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt & Robert I. Soare - 2007 - 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 (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  14.  27
    Computability of Fraïssé Limits.Barbara F. Csima, Valentina S. Harizanov, Russell Miller & Antonio Montalbán - 2011 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  26
    Spaces of Orders and Their Turing Degree Spectra.Malgorzata A. Dabkowska, Mieczyslaw K. Dabkowski, Valentina S. Harizanov & Amir A. Togha - 2010 - Annals of Pure and Applied Logic 161 (9):1134-1143.
    We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s [28] (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  38
    Chains and Antichains in Partial Orderings.Valentina S. Harizanov, Carl G. Jockusch & Julia F. Knight - 2009 - 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 (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  54
    Intrinsic Bounds on Complexity and Definability at Limit Levels.John Chisholm, Ekaterina B. Fokina, Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight & Sara Quinn - 2009 - 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)  
     
    Export citation  
     
    Bookmark   1 citation  
  18. Frequency Computations and the Cardinality Theorem.Valentina Harizanov, Martin Kummer & Jim Owings - 1992 - Journal of Symbolic Logic 57 (2):682-687.
  19.  11
    Regular Relations and the Quantifier “There Exist Uncountably Many”.Zarko Mijajlović & Valentina Harizanov - 1983 - Mathematical Logic Quarterly 29 (3):151-161.
  20.  24
    $\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 (7 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  21.  22
    Spectra of Structures and Relations.Valentina S. Harizanov & Russel G. Miller - 2007 - 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)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  22
    Sequences of N-Diagrams.Valentina S. Harizanov, Julia F. Knight & Andrei S. Morozov - 2002 - Journal of Symbolic Logic 67 (3):1227-1247.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  5
    Π₁¹ 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.
  24.  12
    Carnegie Mellon University, Pittsburgh, PA May 19–23, 2004.John Baldwin, Lev Beklemishev, Michael Hallett, Valentina Harizanov, Steve Jackson, Kenneth Kunen, Angus J. MacIntyre, Penelope Maddy, Joe Miller & Michael Rathjen - 2005 - Bulletin of Symbolic Logic 11 (1).
    Direct download  
     
    Export citation  
     
    Bookmark  
  25.  20
    Σ 1 0 and Π 1 0 Equivalence Structures.Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel - 2011 - Annals of Pure and Applied Logic 162 (7):490-503.
    We study computability theoretic properties of and equivalence structures and how they differ from computable equivalence structures or equivalence structures that belong to the Ershov difference hierarchy. Our investigation includes the complexity of isomorphisms between equivalence structures and between equivalence structures.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  26.  11
    Preface.Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood - 2009 - Archive for Mathematical Logic 48 (1):1-6.
  27.  17
    San Antonio Convention Center San Antonio, Texas January 14–15, 2006.Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, Sergei Starchenko & Valentina Harizanov - 2006 - Bulletin of Symbolic Logic 12 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  28.  15
    Partial Automorphism Semigroups.Jennifer Chubb, Valentina S. Harizanov, Andrei S. Morozov, Sarah Pingrey & Eric Ufferman - 2008 - Annals of Pure and Applied Logic 156 (2):245-258.
    We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism of the subsemigroups yields isomorphism of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a computable structure, up to computable isomorphism, from the isomorphism type of its inverse semigroup of computable (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  29.  10
    Dependence Relations in Computably Rigid Computable Vector Spaces.Rumen D. Dimitrov, Valentina S. Harizanov & Andrei S. Morozov - 2005 - Annals of Pure and Applied Logic 132 (1):97-108.
    We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 570–583 ; 379–387 ].
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  30.  11
    Computability-Theoretic Categoricity and Scott Families.Ekaterina Fokina, Valentina Harizanov & Daniel Turetsky - 2019 - Annals of Pure and Applied Logic 170 (6):699-717.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  31.  41
    New Orleans Marriott and Sheraton New Orleans New Orleans, Louisiana January 7–8, 2007.Matthew Foreman, Su Gao, Valentina Harizanov, Ulrich Kohlenbach, Michael Rathjen, Reed Solomon, Carol Wood & Marcia Groszek - 2007 - Bulletin of Symbolic Logic 13 (3).
    Direct download  
     
    Export citation  
     
    Bookmark  
  32.  4
    Ash C. J. And Knight J.. Computable Structures and the Hyperarithmetical Hierarchy. Studies in Logic and the Foundations of Mathematics, Vol. 144. Elsevier, Amsterdam Etc. 2000, Xv + 346 Pp. [REVIEW]Valentina Harizanov - 2001 - Bulletin of Symbolic Logic 7 (3):383-385.
  33.  25
    Effectively and Noneffectively Nowhere Simple Sets.Valentina S. Harizanov - 1996 - Mathematical Logic Quarterly 42 (1):241-248.
    R. Shore proved that every recursively enumerable set can be split into two nowhere simple sets. Splitting theorems play an important role in recursion theory since they provide information about the lattice ϵ of all r. e. sets. Nowhere simple sets were further studied by D. Miller and J. Remmel, and we generalize some of their results. We characterize r. e. sets which can be split into two effectively nowhere simple sets, and r. e. sets which can be split into (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  34. Of the Association for Symbolic Logic.Valentina Harizanov - 2006 - Bulletin of Symbolic Logic 12 (4).
  35.  8
    Review: C. J. Ash, J. Knight, Computable Structures and the Hyperarithmetical Hierarchy. [REVIEW]Valentina Harizanov - 2001 - Bulletin of Symbolic Logic 7 (3):383-385.
  36.  4
    Review: Sergei S. Goncharov, Countable Boolean Algebras and Decidability. [REVIEW]Valentina Harizanov - 1998 - Journal of Symbolic Logic 63 (3):1188-1190.
  37.  16
    Sergei S. Goncharov. Countable Boolean Algebras and Decidability. English Translation of Schetnye Bulevy Algebry I Razreshimost′. Siberian School of Algebra and Logic. Consultants Bureau, New York, London, and Moscow, 1997, Xii + 318 Pp. [REVIEW]Valentina Harizanov - 1998 - Journal of Symbolic Logic 63 (3):1188-1190.
  38.  9
    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