37 found
Sort by:
  1.  17 DLs
    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  
  2.  11 DLs
    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  
  3.  11 DLs
    Douglas Cenzer (1974). Analytic Inductive Definitions. Journal of Symbolic Logic 39 (2):310-312.
  4.  10 DLs
    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  
  5.  10 DLs
    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 (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  6.  7 DLs
    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 (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7.  7 DLs
    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  
  8.  6 DLs
    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 (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  9.  5 DLs
    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  
  10.  5 DLs
    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  
  11.  3 DLs
    Douglas Cenzer & Jeffrey Remmel (1995). Feasible Graphs and Colorings. 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 (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  12.  3 DLs
    Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King (2008). Computable Symbolic Dynamics. Mathematical Logic Quarterly 54 (5):460-469.
  13.  3 DLs
    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  
  14.  3 DLs
    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  
  15.  3 DLs
    Douglas Cenzer & Farzan Riazati (2005). Minimal Extensions of Π01 Classes. Mathematical Logic Quarterly 51 (2):206-216.
    A minimal extension of a Π01 class P is a Π01 class Q such that P ⊂ Q, Q – P is infinite, and for any Π01 class R, if P ⊂ R ⊂ Q, then either R – P is finite or Q – R is finite; Q is a nontrivial minimal extension of P if in addition P and Q′ have the same Cantor-Bendixson derivative. We show that for any class P which has a single limit point A, (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  16.  2 DLs
    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 (2):145-163.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  17.  2 DLs
    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  
  18.  2 DLs
    Douglas Cenzer & Jeffrey Remmel (1991). Polynomial-Time Versus Recursive Models. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  19.  2 DLs
    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  
  20.  2 DLs
    Douglas Cenzer & Rebecca Weber (2008). Preface. Archive for Mathematical Logic 46 (7-8):529-531.
  21.  1 DLs
    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.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  22.  1 DLs
    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.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  23.  1 DLs
    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) := (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  24.  1 DLs
    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  
  25.  1 DLs
    Douglas Cenzer & Jeffrey Remmel (1998). Index Sets for Π01 Classes. 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 (2 more)  
     
    My bibliography  
     
    Export citation  
  26.  1 DLs
    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  
  27.  0 DLs
    Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood (2009). Preface. Archive for Mathematical Logic 48 (1):1-6.
  28.  0 DLs
    Douglas Cenzer & Peter G. Hinman (2003). Density of the Medvedev Lattice of Π [Sup0][Sub1]. Archive for Mathematical Logic 42 (6).
    Direct download  
     
    My bibliography  
     
    Export citation  
  29.  0 DLs
    Douglas Cenzer (2012). Various Papers on Π01 Classes. Bulletin of Symbolic Logic 18 (3):409.
  30.  0 DLs
    Douglas Cenzer & Jeffrey Remmel (1998). Index Sets for< I> Π_< Sup> 0< Sub> 1 Classes. Annals of Pure and Applied Logic 93 (1):3-61.
    Direct download  
     
    My bibliography  
     
    Export citation  
  31.  0 DLs
    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  
  32.  0 DLs
    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.
    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 (3 more)  
     
    My bibliography  
     
    Export citation  
  33.  0 DLs
    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 (1):3-6.
    No categories
    Direct download  
     
    My bibliography  
     
    Export citation  
  34.  0 DLs
    Douglas Cenzer & Jeffrey Remmel (1992). Polynomial-Time Abelian Groups. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  35.  0 DLs
    Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov (2006). Effective Categoricity of Equivalence Structures. 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 (3 more)  
     
    My bibliography  
     
    Export citation  
  36.  0 DLs
    Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore (1993). Countable Thin Π01 Classes. Annals of Pure and Applied Logic 59 (2):79-139.
    Cenzer, D., R. Downey, C. Jockusch and R.A. Shore, Countable thin Π01 classes, Annals of Pure and Applied Logic 59 79–139. A Π01 class P {0, 1}ω is thin if every Π01 subclass of P is the intersection of P with some clopen set. Countable thin Π01 classes are constructed having arbitrary recursive Cantor- Bendixson rank. A thin Π01 class P is constructed with a unique nonisolated point A and furthermore A is of degree 0’. It is shown that no (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation