35 found
Order:
  1.  48
    Effective categoricity of equivalence structures.Wesley Calvert, Douglas Cenzer, Valentina Harizanov & Andrei Morozov - 2006 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   22 citations  
  2.  52
    Members of countable π10 classes.Douglas Cenzer, Peter Clote, Rick L. Smith, Robert I. Soare & Stanley S. Wainer - 1986 - Annals of Pure and Applied Logic 31:145-163.
  3.  46
    Density of the Medvedev lattice of Π0 1 classes.Douglas Cenzer & Peter G. Hinman - 2003 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   17 citations  
  4.  35
    Countable thin Π01 classes.Douglas Cenzer, Rodney Downey, Carl Jockusch & Richard A. Shore - 1993 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  5.  29
    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   11 citations  
  6.  26
    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   10 citations  
  7.  32
    (1 other version)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   7 citations  
  8.  31
    Effective categoricity of Abelian p -groups.Wesley Calvert, Douglas Cenzer, Valentina S. Harizanov & Andrei Morozov - 2009 - Annals of Pure and Applied Logic 159 (1-2):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 (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  9.  49
    On the ranked points of a Π1 0 set.Douglas Cenzer & Rick L. Smith - 1989 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  10.  81
    Space complexity of Abelian groups.Douglas Cenzer, Rodney G. Downey, Jeffrey B. Remmel & Zia Uddin - 2009 - 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 (5 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  11.  46
    Degrees of difficulty of generalized r.e. separating classes.Douglas Cenzer & Peter G. Hinman - 2008 - 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)  
     
    Export citation  
     
    Bookmark   3 citations  
  12.  22
    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  
     
    Export citation  
     
    Bookmark   3 citations  
  13.  35
    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  
  14.  55
    Cores of Π11 sets of reals.Andreas Blass & Douglas Cenzer - 1974 - Journal of Symbolic Logic 39 (4):649 - 654.
  15.  26
    Monotone inductive definitions over the continuum.Douglas Cenzer - 1976 - Journal of Symbolic Logic 41 (1):188-198.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  61
    Monotone reducibility and the family of infinite sets.Douglas Cenzer - 1984 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  17.  18
    Participants and titles of lectures.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 - Annals of Pure and Applied Logic 94 (1):3-6.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  18.  38
    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 (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  49
    Effectively closed sets and enumerations.Paul Brodhead & Douglas Cenzer - 2008 - 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 (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  20.  46
    Σ 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   1 citation  
  21.  57
    Analytic inductive definitions.Douglas Cenzer - 1974 - Journal of Symbolic Logic 39 (2):310-312.
  22.  56
    A superhigh diamond in the c.e. tt-degrees.Douglas Cenzer, Johanna Ny Franklin, Jiang Liu & Guohua Wu - 2011 - 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 (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  23.  50
    Computable symbolic dynamics.Douglas Cenzer, S. Ali Dashti & Jonathan L. F. King - 2008 - Mathematical Logic Quarterly 54 (5):460-469.
    We investigate computable subshifts and the connection with effective symbolic dynamics. It is shown that a decidable Π01 class P is a subshift if and only if there exists a computable function F mapping 2ℕ to 2ℕ such that P is the set of itineraries of elements of 2ℕ. Π01 subshifts are constructed in 2ℕ and in 2ℤ which have no computable elements. We also consider the symbolic dynamics of maps on the unit interval.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  24.  34
    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  
  25.  42
    Index sets for computable differential equations.Douglas Cenzer & Jeffrey B. Remmel - 2004 - Mathematical Logic Quarterly 50 (4-5):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 (3 more)  
     
    Export citation  
     
    Bookmark  
  26.  91
    Linear orders with distinguished function symbol.Douglas Cenzer, Barbara F. Csima & Bakhadyr Khoussainov - 2009 - 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)  
     
    Export citation  
     
    Bookmark  
  27.  39
    Minimal extensions of Π01 classes.Douglas Cenzer & Farzan Riazati - 2005 - 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 (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  28.  19
    Preface.Douglas Cenzer & Rebecca Weber - 2008 - Archive for Mathematical Logic 46 (7-8):529-531.
  29.  35
    Preface.Douglas Cenzer, Valentina Harizanov, David Marker & Carol Wood - 2009 - Archive for Mathematical Logic 48 (1):1-6.
  30.  19
    Preface.Douglas Cenzer & Jeffrey B. Remmel - 1998 - Annals of Pure and Applied Logic 93 (1-3):1-2.
  31.  32
    San Antonio Convention Center San Antonio, Texas January 14–15, 2006.Douglas Cenzer, C. Ward Henson, Michael C. Laskowski, Alain Louveau, Russell Miller, Itay Neeman, Sergei Starchenko & Valentina Harizanov - 2006 - Bulletin of Symbolic Logic 12 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  32. Various papers on Π01 classes.Douglas Cenzer - 2012 - Bulletin of Symbolic Logic 18 (3):409.
  33. 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  
  34.  9
    (1 other version)Fenstad Jens E.. General recursion theory. An axiomatic approach. Perspectives in mathematical logic. Springer-Verlag, Berlin, Heidelberg, and New York, 1980, XI + 225 pp. [REVIEW]Douglas Cenzer - 1982 - Journal of Symbolic Logic 47 (3):696-698.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  35.  15
    George Barmpalias, Andrew E. M. Lewis and Keng Meng NG. The importance of Π 0 1 classes in effective randomness. The Journal of Symbolic Logic, vol. 75 (2010), pp. 387–400. - George Barmpalias, Andrew E. M. Lewis and Frank Stephan. Π 0 1 classes, LR degrees and Turing degrees. Annals of Pure and Applied Logic, vol. 156 (2008), pp. 21–38. - Antonin Kučera. Measure, Π 0 1 classes and complete extensions of PA. Recursion Theory Week (Oberwofach, 1984). Lecture Notes in Mathematics, vol. 1141. Springer, Berlin, 1985, pp. 245–259. - Frank Stephan. Martin-Löf randomness and PA complete sets. Logic Colloquium '02. Lecture Notes in Logic, vol. 27, Association for Symbolic Logic, La Jolla, CA, 2006, pp. 342–348. [REVIEW]Douglas Cenzer - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark