Switch to: References

Add citations

You must login to add citations.
  1. The complexity of recursive constraint satisfaction problems.Victor W. Marek & Jeffrey B. Remmel - 2010 - 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  
  • On degree-preserving homeomorphisms between trees in computable topology.Iraj Kalantari & Larry Welch - 2008 - Archive for Mathematical Logic 46 (7-8):679-693.
    In this paper we first give a variant of a theorem of Jockusch–Lewis– Remmel on existence of a computable, degree-preserving homeomorphism between a bounded strong ${\Pi^0_2}$ class and a bounded ${\Pi^0_1}$ class in 2 ω . Namely, we show that for mathematically common and interesting topological spaces, such as computably presented ${\mathbb{R}^n}$ , we can obtain a similar result where the homeomorphism is in fact the identity mapping. Second, we apply this finding to give a new, priority-free proof of existence (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • A blend of methods of recursion theory and topology: A Π1 0 tree of shadow points. [REVIEW]Iraj Kalantari & Larry Welch - 2004 - Archive for Mathematical Logic 43 (8):991-1008.
    This paper is a sequel to our [7]. In that paper we constructed a Π1 0 tree of avoidable points. Here we construct a Π1 0 tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2<ω. One interesting fact is that while our Π1 0 tree (...)
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • On notions of computability-theoretic reduction between Π21 principles.Denis R. Hirschfeldt & Carl G. Jockusch - 2016 - Journal of Mathematical Logic 16 (1):1650002.
    Several notions of computability-theoretic reducibility between [Formula: see text] principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey’s Theorem and related principles under these notions. Among other results, we show that for each [Formula: see text], there is an instance of RT[Formula: see text] all of whose solutions have PA degree over [Formula: see text] and use this to show that König’s Lemma lies strictly between RT[Formula: see text] and RT[Formula: see (...)
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  • 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 (2 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  • Index sets for< i> Π_< sup> 0< sub> 1 classes.Douglas Cenzer & Jeffrey Remmel - 1998 - Annals of Pure and Applied Logic 93 (1):3-61.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
    		•
  • 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