28 found
Order:
Disambiguations
Jeffrey B. Remmel [19]Jeffrey Remmel [11]
  1.  6
    A Survey of Lattices of Re Substructures.Anil Nerode & Jeffrey Remmel - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--323.
    Direct download  
     
    Export citation  
     
    Bookmark   14 citations  
  2.  11
    Polynomial-Time Versus Recursive Models.Douglas Cenzer & Jeffrey Remmel - 1991 - Annals of Pure and Applied Logic 54 (1):17-58.
    The central problem considered in this paper is whether a given recursive structure is recursively isomorphic to a polynomial-time structure. Positive results are obtained for all relational structures, for all Boolean algebras and for the natural numbers with addition, multiplication and the unary function 2x. Counterexamples are constructed for recursive structures with one unary function and for Abelian groups and also for relational structures when the universe of the structure is fixed. Results are also given which distinguish primitive recursive structures, (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   8 citations  
  3.  15
    Polynomial-Time Abelian Groups.Douglas Cenzer & Jeffrey Remmel - 1992 - Annals of Pure and Applied Logic 56 (1-3):313-363.
    This paper is a continuation of the authors' work , where the main problem considered was whether a given recursive structure is recursively isomorphic to a polynomial-time structure. In that paper, a recursive Abelian group was constructed which is not recursively isomorphic to any polynomial-time Abelian group. We now show that if every element of a recursive Abelian group has finite order, then the group is recursively isomorphic to a polynomial-time group. Furthermore, if the orders are bounded, then the group (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  4.  56
    Space Complexity of Abelian Groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2008 - 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 (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  5.  13
    Equivalence Structures and Isomorphisms in the Difference Hierarchy.Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel - 2009 - Journal of Symbolic Logic 74 (2):535-556.
    We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  6.  25
    Recursive Boolean Algebras with Recursive Atoms.Jeffrey B. Remmel - 1981 - Journal of Symbolic Logic 46 (3):595-616.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   5 citations  
  7.  13
    Index Sets for Π01 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):3-61.
    A Π01 class is an effectively closed set of reals. We study properties of these classes determined by cardinality, measure and category as well as by the complexity of the members of a class P. Given an effective enumeration {Pe:e < ω} of the Π01 classes, the index set I for a certain property is the set of indices e such that Pe has the property. For example, the index set of binary Π01 classes of positive measure is Σ02 complete. (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  8.  10
    On Speedable and Levelable Vector Spaces.Frank A. Bäuerle & Jeffrey B. Remmel - 1994 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  7
    Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
    The problem of when a recursive graph has a recursive k-coloring has been extensively studied by Bean, Schmerl, Kierstead, Remmel, and others. In this paper, we study the polynomial time analogue of that problem. We develop a number of negative and positive results about colorings of polynomial time graphs. For example, we show that for any recursive graph G and for any k, there is a polynomial time graph G′ whose vertex set is {0,1}* such that there is an effective (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  10.  14
    Algorithmic Randomness of Continuous Functions.George Barmpalias, Paul Brodhead, Douglas Cenzer, Jeffrey B. Remmel & Rebecca Weber - 2008 - 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}}$ , (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  11.  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  
  12.  8
    J. Donald Monk. Mathematical Logic. Graduate Texts in Mathematics, No. 37. Springer-Verlag, New York, Heidelberg, and Berlin, 1976, X + 531 Pp. [REVIEW]Jeffrey B. Remmel - 1979 - Journal of Symbolic Logic 44 (2):283-284.
  13.  70
    Complexity, Decidability and Completeness.Douglas Cenzer & Jeffrey B. Remmel - 2006 - 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 (6 more)  
     
    Export citation  
     
    Bookmark  
  14.  30
    Nonmonotonic Rule Systems with Recursive Sets of Restraints.V. Wiktor Marek, Anil Nerode & Jeffrey B. Remmel - 1997 - Archive for Mathematical Logic 36 (4-5):339-384.
  15.  8
    McNaughton Games and Extracting Strategies for Concurrent Programs.Anil Nerode, Jeffrey B. Remmel & Alexander Yakhnis - 1996 - Annals of Pure and Applied Logic 78 (1-3):203-242.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  16.  8
    Recursively Rigid Boolean Algebras.Jeffrey B. Remmel - 1987 - Annals of Pure and Applied Logic 36 (1):39-52.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  17.  16
    Index Sets for Computable Differential Equations.Douglas Cenzer & Jeffrey B. Remmel - 2004 - Mathematical Logic Quarterly 50 (45):329-344.
    Index sets are used to measure the complexity of properties associated with the differentiability of real functions and the existence of solutions to certain classic differential equations. The new notion of a locally computable real function is introduced and provides several examples of Σ04 complete sets.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  18.  16
    San Diego Convention Center, San Diego, CA January 8–9, 2008.Gregory L. Cherlin, Ilijas Farah, Pavel Hrubes, Victor Marek, Jan Riemann, Simon Thomas & Jeffrey Remmel - 2008 - Bulletin of Symbolic Logic 14 (3).
  19.  13
    The Undecidability of the Lattice of R.E. Closed Subsets of an Effective Topological Space.Sheryl Silibovsky Brady & Jeffrey B. Remmel - 1987 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  20.  17
    The Complexity of Recursive Constraint Satisfaction Problems.Victor W. Marek & Jeffrey B. Remmel - 2009 - 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 (5 more)  
     
    Export citation  
     
    Bookmark  
  21.  15
    Index Sets for Ω‐Languages.Douglas Czenzer & Jeffrey B. Remmel - 2003 - 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 (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  22.  15
    Partial Orderings of Fixed Finite Dimension: Model Companions and Density.Alfred B. Manaster & Jeffrey B. Remmel - 1981 - Journal of Symbolic Logic 46 (4):789-802.
  23.  13
    Feasible Graphs with Standard Universe.Douglas Cenzer & Jeffrey B. Remmel - 1998 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  24.  10
    Hybrid Answer Set Programming.Alex Brik & Jeffrey Remmel - 2014 - Annals of Pure and Applied Logic 165 (1):134-163.
    This paper discusses an extension of Answer Set Programming called Hybrid Answer Set Programming which allows the user to reason about dynamical systems that exhibit both discrete and continuous aspects. The unique feature of Hybrid ASP is that it allows the use of ASP type rules as controls for when to apply algorithms to advance the system to the next position. That is, if the prerequisites of a rule are satisfied and the constraints of the rule are not violated, then (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  25.  10
    2007-2008 Winter Meeting of the Association for Symbolic Logic.Jeffrey Remmel - 2008 - Bulletin of Symbolic Logic 14 (3):402-411.
  26.  9
    Index Sets for< I> Π_< Sup> 0< Sub> 1 Classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1):3-61.
  27.  11
    Preface.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):1-2.
  28.  6
    Review: J. Donald Monk, Mathematical Logic. [REVIEW]Jeffrey B. Remmel - 1979 - Journal of Symbolic Logic 44 (2):283-284.