27 found
Order:
  1. Rodney G. Downey, Geoffrey L. Laforte & Richard A. Shore (2003). Decomposition and Infima in the Computably Enumerable Degrees. Journal of Symbolic Logic 68 (2):551-579.
    Given two incomparable c.e. Turing degrees a and b, we show that there exists a c.e. degree c such that c = (a ⋃ c) ⋂ (b ⋃ c), a ⋃ c | b ⋃ c, and c < a ⋃ b.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography  
  2.  1
    Rodney G. Downey, Carl G. Jockusch & Paul E. Schupp (2013). Asymptotic Density and Computably Enumerable Sets. Journal of Mathematical Logic 13 (2):1350005.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  3.  9
    Rodney G. Downey, Sergei S. Goncharov, Asher M. Kach, Julia F. Knight, Oleg V. Kudinov, Alexander G. Melnikov & Daniel Turetsky (2010). Decidability and Computability of Certain Torsion-Free Abelian Groups. Notre Dame Journal of Formal Logic 51 (1):85-96.
    We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography   2 citations  
  4.  6
    Rodney G. Downey & Evan J. Griffiths (2004). Schnorr Randomness. Journal of Symbolic Logic 69 (2):533 - 554.
    Schnorr randomness is a notion of algorithmic randomness for real numbers closely related to Martin-Löf randomness. After its initial development in the 1970s the notion received considerably less attention than Martin-Löf randomness, but recently interest has increased in a range of randomness concepts. In this article, we explore the properties of Schnorr random reals, and in particular the c.e. Schnorr random reals. We show that there are c.e. reals that are Schnorr random but not Martin-Löf random, and provide a new (...)
    Direct download (5 more)  
     
    Export citation  
     
    My bibliography   4 citations  
  5.  5
    Rodney G. Downey, Steffen Lempp & Richard A. Shore (1993). Highness and Bounding Minimal Pairs. Mathematical Logic Quarterly 39 (1):475-491.
  6.  3
    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)  
     
    Export citation  
     
    My bibliography   6 citations  
  7.  26
    Rodney G. Downey, Bart Kastermans & Steffen Lempp (2009). On Computable Self-Embeddings of Computable Linear Orderings. Journal of Symbolic Logic 74 (4):1352 - 1366.
    We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography  
  8.  13
    Peter A. Cholak, Rodney Downey & Leo A. Harrington (2008). The Complexity of Orbits of Computably Enumerable Sets. Bulletin of Symbolic Logic 14 (1):69 - 87.
    The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, ε, such that the question of membership in this orbit is ${\Sigma _1^1 }$ -complete. This result and proof have a number of nice corollaries: the Scott rank of ε is $\omega _1^{{\rm{CK}}}$ + 1; not all orbits are elementarily definable; there is no arithmetic description of all orbits of ε; for all finite α ≥ 9, there is a properly $\Delta (...)
    Direct download (6 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  9.  1
    Rodney Downey, Alexander G. Melnikov & Keng Meng Ng (forthcoming). Abelian P-Groups and the Halting Problem. Annals of Pure and Applied Logic.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  10.  20
    Rodney G. Downey & Steffen Lempp (1997). Contiguity and Distributivity in the Enumerable Turing Degrees. Journal of Symbolic Logic 62 (4):1215-1240.
    We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
    Direct download (8 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  11.  21
    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)  
     
    Export citation  
     
    My bibliography  
  12.  12
    Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows (1997). On the Parameterized Complexity of Short Computation and Factorization. Archive for Mathematical Logic 36 (4-5):321-337.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  13.  2
    Karl A. Abrahamson, Rodney G. Downey & Michael R. Fellows (1995). Fixed-Parameter Tractability and Completeness IV: On Completeness for W[P] and PSPACE Analogues. Annals of Pure and Applied Logic 73 (3):235-276.
    We describe new results in parametrized complexity theory. In particular, we prove a number of concrete hardness results for W[P], the top level of the hardness hierarchy introduced by Downey and Fellows in a series of earlier papers. We also study the parametrized complexity of analogues of PSPACE via certain natural problems concerning k-move games. Finally, we examine several aspects of the structural complexity of W [P] and related classes. For instance, we show that W[P] can be characterized in terms (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   3 citations  
  14.  4
    Rodney G. Downey & Michael F. Moses (1989). On Choice Sets and Strongly Non-Trivial Self-Embeddings of Recursive Linear Orders. Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (3):237-246.
    No categories
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  15.  11
    Rodney G. Downey & Asher M. Kach (2010). Euclidean Functions of Computable Euclidean Domains. Notre Dame Journal of Formal Logic 52 (2):163-172.
    We study the complexity of (finitely-valued and transfinitely-valued) Euclidean functions for computable Euclidean domains. We examine both the complexity of the minimal Euclidean function and any Euclidean function. Additionally, we draw some conclusions about the proof-theoretical strength of minimal Euclidean functions in terms of reverse mathematics.
    Direct download (4 more)  
     
    Export citation  
     
    My bibliography  
  16.  7
    Liming Cai, Jianer Chen, Rodney G. Downey & Michael R. Fellows (1997). Advice Classes of Parameterized Tractability. Annals of Pure and Applied Logic 84 (1):119-138.
    Many natural computational problems have input consisting of two or more parts, one of which may be considered a parameter. For example, there are many problems for which the input consists of a graph and a positive integer. A number of results are presented concerning parameterized problems that can be solved in complexity classes below P, given a single word of advice for each parameter value. Different ways in which the word of advice can be employed are considered, and it (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  17. Rodney G. Downey, Carl Jockusch & Joseph S. Miller (2006). On Self-Embeddings of Computable Linear Orderings. Annals of Pure and Applied Logic 138 (1):52-76.
    The Dushnik–Miller Theorem states that every infinite countable linear ordering has a nontrivial self-embedding. We examine computability-theoretical aspects of this classical theorem.
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  18. Liang Yu, Decheng Ding & Rodney Downey (2004). The Kolmogorov Complexity of Random Reals. Annals of Pure and Applied Logic 129 (1-3):163-180.
    We investigate the initial segment complexity of random reals. Let K denote prefix-free Kolmogorov complexity. A natural measure of the relative randomness of two reals α and β is to compare complexity K and K. It is well-known that a real α is 1-random iff there is a constant c such that for all n, Kn−c. We ask the question, what else can be said about the initial segment complexity of random reals. Thus, we study the fine behaviour of K (...)
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography   1 citation  
  19.  2
    Rodney G. Downey, Guohua Wu & Yue Yang (2015). The Members of Thin and Minimal Π 1 0 Classes, Their Ranks and Turing Degrees. Annals of Pure and Applied Logic 166 (7-8):755-766.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  20.  6
    Rodney G. Downey & Steffen Lempp (2002). Contiguity and Distributivity in the Enumerable Turing Degrees: Corrigendum. Journal of Symbolic Logic 67 (4):1579-1580.
  21.  1
    Rodney G. Downey & Michael F. Moses (1989). On Choice Sets and Strongly Non‐Trivial Self‐Embeddings of Recursive Linear Orders. Mathematical Logic Quarterly 35 (3):237-246.
  22.  4
    Rodney G. Downey & Steffen Lempp (1994). There is No Plus-Capping Degree. Archive for Mathematical Logic 33 (2):109-119.
    Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    My bibliography  
  23. Eberhard Herrmann & Rodney Downey (1990). Review: Robert I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. [REVIEW] Journal of Symbolic Logic 55 (1):356-357.
     
    Export citation  
     
    My bibliography  
  24.  4
    Rodney G. Downey & Steffen Lempp (2002). Corrigendum: ``Contiguity and Distributivity in the Enumerable Turing Degrees''. Journal of Symbolic Logic 67 (4):1579-1580.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  25. Rodney& Griffiths Downey (2004). Evan," Schnorr Randomness. Journal of Symbolic Logic 69:2.
    No categories
     
    Export citation  
     
    My bibliography  
  26. Rodney Downey, Ieke Moerdijk, Boban Velickovic, Samson Abramsky, Marat Arslanov, Harvey Friedman, Martin Goldstern, Ehud Hrushovski, Jochen Koenigsmann & Andy Lewis (2007). Nijmegen, The Netherlands July 27–August 2, 2006. Bulletin of Symbolic Logic 13 (2).
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography  
  27. Eberhard Herrmann & Rodney Downey (1990). Soare Robert I.. Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, Heidelberg, New York, Etc., 1987, Xviii + 437 Pp. [REVIEW] Journal of Symbolic Logic 55 (1):356-357.
    Direct download (2 more)  
     
    Export citation  
     
    My bibliography