You are accessing PhilPapers from Open University (UK), an institution that is not subscribed to PhilPapers. Starting on July 1, 2014, we ask institutions that grant philosophy degrees and are based in high-GDP countries to contribute to PhilPapers' maintenance and development through a subscription. See this page for details. Please show your support by contacting your librarian.
37 found
Sort by:
  1. Douglas Cenzer (2012). Various Papers on Π01 Classes. Bulletin of Symbolic Logic 18 (3):409.
     
    My bibliography  
     
    Export citation  
  2. Douglas Cenzer, Johanna Ny Franklin, Jiang Liu & Guohua Wu (2011). A Superhigh Diamond in the Ce Tt-Degrees. Archive for Mathematical Logic 50 (1-2):33-44.
    The notion of superhigh computably enumerable (c.e.) degrees was first introduced by (Mohrherr in Z Math Logik Grundlag Math 32: 5–12, 1986) where she proved the existence of incomplete superhigh c.e. degrees, and high, but not superhigh, c.e. degrees. Recent research shows that the notion of superhighness is closely related to algorithmic randomness and effective measure theory. Jockusch and Mohrherr proved in (Proc Amer Math Soc 94:123–128, 1985) that the diamond lattice can be embedded into the c.e. tt-degrees preserving 0 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Douglas Cenzer, Valentina Harizanov & Jeffrey B. Remmel (2011). And Equivalence Structures. Annals of Pure and Applied Logic 162 (7):490-503.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. 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  
  5. Douglas Cenzer, Barbara F. Csima & Bakhadyr Khoussainov (2009). Linear Orders with Distinguished Function Symbol. Archive for Mathematical Logic 48 (1):63-76.
    We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6. 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  
  7. Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood (2009). Preface. Archive for Mathematical Logic 48 (1):1-6.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Douglas Cenzer, Geoffrey LaForte & Jeffrey Remmel (2009). Equivalence Structures and Isomorphisms in the Difference Hierarchy. 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 (4 more)  
     
    My bibliography  
     
    Export citation  
  9. 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  
  10. Paul Brodhead & Douglas Cenzer (2008). Effectively Closed Sets and Enumerations. Archive for Mathematical Logic 46 (7-8):565-582.
    An effectively closed set, or ${\Pi^{0}_{1}}$ class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of ${\Pi^{0}_{1}}$ classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of ${\Pi^{0}_{1}}$ classes and (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  11. Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King (2008). Computable Symbolic Dynamics. Mathematical Logic Quarterly 54 (5):460-469.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Douglas Cenzer & Peter G. Hinman (2008). Degrees of Difficulty of Generalized R.E. Separating Classes. Archive for Mathematical Logic 46 (7-8):629-647.
    Important examples of $\Pi^0_1$ classes of functions $f \in {}^\omega\omega$ are the classes of sets (elements of ω 2) which separate a given pair of disjoint r.e. sets: ${\mathsf S}_2(A_0, A_1) := \{f \in{}^\omega2 : (\forall i < 2)(\forall x \in A_i)f(x) \neq i\}$ . A wider class consists of the classes of functions f ∈ ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: ${\mathsf S}_k(A_0,\ldots,A_k-1) := (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  13. Douglas Cenzer & Rebecca Weber (2008). Preface. Archive for Mathematical Logic 46 (7-8):529-531.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov (2006). Effective Categoricity of Equivalence Structures. Annals of Pure and Applied Logic 141 (1):61-78.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  15. Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, Sergei Starchenko & Valentina Harizanov (2006). San Antonio Convention Center San Antonio, Texas January 14–15, 2006. Bulletin of Symbolic Logic 12 (4).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  16. 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  
  17. Douglas Cenzer & Farzan Riazati (2005). Minimal Extensions of Π01 Classes. Mathematical Logic Quarterly 51 (2):206-216.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  18. Douglas Cenzer & Peter G. Hinman (2003). Density of the Medvedev Lattice of Π0 1 Classes. Archive for Mathematical Logic 42 (6):583-600.
    The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Douglas Cenzer & Peter G. Hinman (2003). Density of the Medvedev Lattice of Π [Sup0][Sub1]. Archive for Mathematical Logic 42 (6).
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  20. Douglas Cenzer & Andre Nies (2001). Initial Segments of the Lattice of Π01 Classes. Journal of Symbolic Logic 66 (4):1749 - 1765.
    We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we obtain (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  21. Klaus Ambos-Spies, Marat Arslanov, Douglas Cenzer, Peter Cholak, Chi Tat Chong, Decheng Ding, Rod Downey, Peter A. Fejer, Sergei S. Goncharov & Edward R. Griffor (1998). Participants and Titles of Lectures. Annals of Pure and Applied Logic 94:3-6.
    No categories
     
    My bibliography  
     
    Export citation  
  22. Douglas Cenzer & Jeffrey Remmel (1998). Index Sets for Π01 Classes. Annals of Pure and Applied Logic 93 (1-3):3-61.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Douglas Cenzer & Jeffrey Remmel (1998). Index Sets for< I> Π_< Sup> 0< Sub> 1 Classes. Annals of Pure and Applied Logic 93 (1):3-61.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  24. Douglas Cenzer & Jeffrey B. Remmel (1998). Feasible Graphs with Standard Universe. Annals of Pure and Applied Logic 94 (1-3):21-35.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  25. Douglas Cenzer & Jeffrey B. Remmel (1998). Preface. Annals of Pure and Applied Logic 93 (1-3):1-2.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  26. Douglas Cenzer & Jeffrey Remmel (1995). Feasible Graphs and Colorings. Mathematical Logic Quarterly 41 (3):327-352.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  27. Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore (1993). Countable Thin Π01 Classes. Annals of Pure and Applied Logic 59 (2):79-139.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. Douglas Cenzer & Jeffrey Remmel (1992). Polynomial-Time Abelian Groups. Annals of Pure and Applied Logic 56 (1-3):313-363.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  29. Douglas Cenzer & Jeffrey Remmel (1991). Polynomial-Time Versus Recursive Models. Annals of Pure and Applied Logic 54 (1):17-58.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  30. Douglas Cenzer & Rick L. Smith (1989). On the Ranked Points of a Π01 Set. Journal of Symbolic Logic 54 (3):975 - 991.
    This paper continues joint work of the authors with P. Clote, R. Soare and S. Wainer (Annals of Pure and Applied Logic, vol. 31 (1986), pp. 145--163). An element x of the Cantor space 2 ω is said have rank α in the closed set P if x is in $D^\alpha(P)\backslash D^{\alpha + 1}(P)$ , where D α is the iterated Cantor-Bendixson derivative. The rank of x is defined to be the least α such that x has rank α in (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  31. Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer (1986). Members of Countable Π10 Classes. Annals of Pure and Applied Logic 31:145-163.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  32. Douglas Cenzer (1984). Monotone Reducibility and the Family of Infinite Sets. Journal of Symbolic Logic 49 (3):774-782.
    Let A and B be subsets of the space 2 N of sets of natural numbers. A is said to be Wadge reducible to B if there is a continuous map Φ from 2 N into 2 N such that A = Φ -1 (B); A is said to be monotone reducible to B if in addition the map Φ is monotone, that is, $a \subset b$ implies $\Phi (a) \subset \Phi(b)$ . The set A is said to be monotone (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  33. Douglas Cenzer (1982). Review: Jens E. Fenstad, General Recursion Theory. An Axiomatic Approach. [REVIEW] Journal of Symbolic Logic 47 (3):696-698.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  34. Douglas Cenzer (1976). Monotone Inductive Definitions Over the Continuum. Journal of Symbolic Logic 41 (1):188-198.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  35. Andreas Blass & Douglas Cenzer (1974). Cores of Π11 Sets of Reals. Journal of Symbolic Logic 39 (4):649 - 654.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  36. Douglas Cenzer (1974). Analytic Inductive Definitions. Journal of Symbolic Logic 39 (2):310-312.