•  12
    Belegradek, O., Verbovskiy, V. and Wagner, FO, Coset
    with J. Y. Halpern, B. M. Kapron, U. Kohlenbach, P. Oliva, F. Lucas, B. Luttik, P. Matet, and M. Pourmahdian
    Annals of Pure and Applied Logic 121 (1): 287. 2003.
  •  9
    On Cohesive Powers of Linear Orders
    with Rumen Dimitrov, Andrey Morozov, Paul Shafer, Alexandra A. Soskova, and Stefan V. Vatev
    Journal of Symbolic Logic 88 (3): 947-1004. 2023.
    Cohesive powersof computable structures are effective analogs of ultrapowers, where cohesive sets play the role of ultrafilters. Let$\omega $,$\zeta $, and$\eta $denote the respective order-types of the natural numbers, the integers, and the rationals when thought of as linear orders. We investigate the cohesive powers of computable linear orders, with special emphasis on computable copies of$\omega $. If$\mathcal {L}$is a computable copy of$\omega $that is computably isomorphic to the usual pre…Read more
  •  7
    Interpreting a Field in its Heisenberg Group
    with Rachael Alvir, Wesley Calvert, Grant Goodman, Julia Knight, Russell Miller, Andrey Morozov, Alexandra Soskova, and Rose Weisshaar
    Journal of Symbolic Logic 87 (3): 1215-1230. 2022.
    We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, Melnikov, R. Miller, and Mo…Read more
  •  4
    On the isomorphism problem for some classes of computable algebraic structures
    with Steffen Lempp, Charles F. D. McCoy, Andrei S. Morozov, and Reed Solomon
    Archive for Mathematical Logic 61 (5): 813-825. 2022.
    We establish that the isomorphism problem for the classes of computable nilpotent rings, distributive lattices, nilpotent groups, and nilpotent semigroups is \-complete, which is as complicated as possible. The method we use is based on uniform effective interpretations of computable binary relations into computable structures from the corresponding algebraic classes.
  •  2
    Logic and Algebraic Structures in Quantum Computing (edited book)
    with Jennifer Chubb and Ali Eskandarian
    Cambridge University Press. 2014.
    Experts in the field explore the connections across physics, quantum logic, and quantum computing.
  •  5
  •  15
    Computability-theoretic categoricity and Scott families
    with Ekaterina Fokina and Daniel Turetsky
    Annals of Pure and Applied Logic 170 (6): 699-717. 2019.
  • Induction, algorithmic learning theory, and philosophy (edited book)
    with Michele Friend and Norma B. Goethe
    Springer. 2007.
  •  27
    Σ 1 0 and Π 1 0 equivalence structures
    with Douglas Cenzer and Jeffrey B. Remmel
    Annals of Pure and Applied Logic 162 (7): 490-503. 2011.
    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
  •  43
    Enumerations in computable structure theory
    with Sergey Goncharov, Julia Knight, Charles McCoy, Russell Miller, and Reed Solomon
    Annals of Pure and Applied Logic 136 (3): 219-246. 2005.
    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 com…Read more
  •  43
    Degree spectra of the successor relation of computable linear orderings
    with Jennifer Chubb and Andrey Frolov
    Archive for Mathematical Logic 48 (1): 7-13. 2009.
    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
  •  15
    Uncountable degree spectra
    Annals of Pure and Applied Logic 54 (3): 255-263. 1991.
    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
  •  14
    Dependence relations in computably rigid computable vector spaces
    with Rumen D. Dimitrov and Andrei S. Morozov
    Annals of Pure and Applied Logic 132 (1): 97-108. 2005.
    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 ]
  •  15
    Preface
    with Douglas Cenzer, David Marker, and Carol Wood
    Archive for Mathematical Logic 48 (1): 1-6. 2009.
  •  28
    Spectra of Structures and Relations
    with Russel G. Miller
    Journal of Symbolic Logic 72 (1). 2007.
    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 to answer a question of Goncharov, an…Read more
  •  43
    Turing degrees of certain isomorphic images of computable relations
    Annals of Pure and Applied Logic 93 (1-3): 103-113. 1998.
    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 contain every Turing degree. These conditions imply that if every Turing degre…Read more
  •  207
    Frequency computations and the cardinality theorem
    with Martin Kummer and Jim Owings
    Journal of Symbolic Logic 57 (2): 682-687. 1992.
  •  7
    Π₁¹ Relations and Paths through ᵊ
    with Sergey S. Goncharov, Julia F. Knight, and Richard A. Shore
    Journal of Symbolic Logic 69 (2). 2004.
  •  17
    Partial automorphism semigroups
    with Jennifer Chubb, Andrei S. Morozov, Sarah Pingrey, and Eric Ufferman
    Annals of Pure and Applied Logic 156 (2): 245-258. 2008.
    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 c…Read more
  •  40
    Bounding Homogeneous Models
    with Barbara F. Csima, Denis R. Hirschfeldt, and Robert I. Soare
    Journal of Symbolic Logic 72 (1). 2007.
    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 single CD theory T such that every homogene…Read more
  •  30
    $\Pi _{1}^{0}$ Classes and Strong Degree Spectra of Relations
    with John Chisholm, Jennifer Chubb, Denis R. Hirschfeldt, Carl G. Jockusch, Timothy McNicholl, and Sarah Pingrey
    Journal of Symbolic Logic 72 (3). 2007.
    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
  •  13
    Some effects of Ash–Nerode and other decidability conditions on degree spectra
    Annals of Pure and Applied Logic 55 (1): 51-65. 1991.
    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 intrinsically r.e. if and only if a natural recursive-syntacti…Read more
  •  43
    Chains and antichains in partial orderings
    with Carl G. Jockusch and Julia F. Knight
    Archive for Mathematical Logic 48 (1): 39-53. 2009.
    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 is a computa…Read more
  •  55
    Isomorphism relations on computable structures
    with Ekaterina B. Fokina, Sy-David Friedman, Julia F. Knight, Charles Mccoy, and Antonio Montalbán
    Journal of Symbolic Logic 77 (1): 122-132. 2012.
    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 ω
  •  23
    San Antonio Convention Center San Antonio, Texas January 14–15, 2006
    with Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, and Sergei Starchenko
    Bulletin of Symbolic Logic 12 (4). 2006.
  •  13
    Turing degrees of hypersimple relations on computable structures
    Annals of Pure and Applied Logic 121 (2-3): 209-226. 2003.
    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 d…Read more