16 found
Sort by:
  1. Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel (2011). And Equivalence Structures. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin (2009). Space Complexity of Abelian Groups. Archive for Mathematical Logic 48 (1):115-140.
    We develop a theory of LOGSPACE structures and apply it to construct a number of examples of Abelian Groups which have LOGSPACE presentations. We show that all computable torsion Abelian groups have LOGSPACE presentations and we show that the groups ${\mathbb {Z}, Z(p^{\infty})}$ , and the additive group of the rationals have LOGSPACE presentations over a standard universe such as the tally representation and the binary representation of the natural numbers. We also study the effective categoricity of such groups. For (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Victor W. Marek & Jeffrey B. Remmel (2009). The Complexity of Recursive Constraint Satisfaction Problems. Annals of Pure and Applied Logic 161 (3):447-457.
    We investigate the complexity of finding solutions to infinite recursive constraint satisfaction problems. We show that, in general, the problem of finding a solution to an infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through a recursive tree. We also identify natural classes of infinite recursive constraint satisfaction problems where the problem of finding a solution to the infinite recursive constraint satisfaction problem is equivalent to the problem of finding an infinite path through (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber (2008). Algorithmic Randomness of Continuous Functions. Archive for Mathematical Logic 46 (7-8):533-546.
    We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}$ of continuous functions on ${2^{\mathbb N}}$ . A probability measure is given and a version of the Martin-Löf test for randomness is defined. Random ${\Delta^0_2}$ continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any ${y \in 2^{\mathbb N}}$ , (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Douglas Cenzer & Jeffrey B. Remmel (2006). Complexity, Decidability and Completeness. Journal of Symbolic Logic 71 (2):399 - 424.
    We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. Douglas Czenzer & Jeffrey B. Remmel (2003). Index Sets for Ω‐Languages. Mathematical Logic Quarterly 49 (1):22-33.
    An ω-language is a set of infinite sequences on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the equation image languages, may enumerated as P0, P1, … and then an index set associated to a given property R (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  7. Douglas Cenzer & Jeffrey B. Remmel (1998). Feasible Graphs with Standard Universe. Annals of Pure and Applied Logic 94 (1-3):21-35.
    A computable graph is constructed which is not computably isomorphic to any polynomial-time graph with a standard universe . Conditions are given under which a computable graph is computably isomorphic to a polynomial-time graph with a standard universe — for example, if every vertex has finite degree. Two special types of graphs are studied. It is shown that any computable tree is recursively isomorphic to a p-time tree with standard universe and that any computable equivalence relation is computably isomorphic to (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Douglas Cenzer & Jeffrey B. Remmel (1998). Preface. Annals of Pure and Applied Logic 93 (1-3):1-2.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. V. Wiktor Marek, Anil Nerode & Jeffrey B. Remmel (1997). Nonmonotonic Rule Systems with Recursive Sets of Restraints. Archive for Mathematical Logic 36 (4-5):339-384.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. Anil Nerode, Jeffrey B. Remmel & Alexander Yakhnis (1996). McNaughton Games and Extracting Strategies for Concurrent Programs. Annals of Pure and Applied Logic 78 (1-3):203-242.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Frank A. Bäuerle & Jeffrey B. Remmel (1994). On Speedable and Levelable Vector Spaces. Annals of Pure and Applied Logic 67 (1-3):61-112.
    In this paper, we study the lattice of r.e. subspaces of a recursively presented vector space V ∞ with regard to the various complexity-theoretic speed-up properties such as speedable, effectively speedable, levelable, and effectively levelable introduced by Blum and Marques. In particular, we study the interplay between an r.e. basis A for a subspace V of V ∞ and V with regard to these properties. We show for example that if A or V is speedable , then V is levelable (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Jeffrey B. Remmel (1987). Recursively Rigid Boolean Algebras. Annals of Pure and Applied Logic 36 (1):39-52.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  13. Sheryl Silibovsky Brady & Jeffrey B. Remmel (1987). The Undecidability of the Lattice of R.E. Closed Subsets of an Effective Topological Space. Annals of Pure and Applied Logic 35 (2):193-203.
    The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Alfred B. Manaster & Jeffrey B. Remmel (1981). Partial Orderings of Fixed Finite Dimension: Model Companions and Density. Journal of Symbolic Logic 46 (4):789-802.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  15. Jeffrey B. Remmel (1981). Recursive Boolean Algebras with Recursive Atoms. Journal of Symbolic Logic 46 (3):595-616.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16. Jeffrey B. Remmel (1979). Review: J. Donald Monk, Mathematical Logic. [REVIEW] Journal of Symbolic Logic 44 (2):283-284.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation