9 found
Sort by:
  1. Klaus Ambos-Spies & Peter A. Fejer (2001). Embeddings of and the Contiguous Degrees. Annals of Pure and Applied Logic 112 (2-3):151-188.
    Downey and Lempp 1215–1240) have shown that the contiguous computably enumerable degrees, i.e. the c.e. Turing degrees containing only one c.e. weak truth-table degree, can be characterized by a local distributivity property. Here we extend their result by showing that a c.e. degree a is noncontiguous if and only if there is an embedding of the nonmodular 5-element lattice N5 into the c.e. degrees which maps the top to the degree a. In particular, this shows that local nondistributivity coincides with (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Peter A. Fejer & Richard A. Shore (2001). Every Incomplete Computably Enumerable Truth-Table Degree is Branching. Archive for Mathematical Logic 40 (2):113-123.
    If r is a reducibility between sets of numbers, a natural question to ask about the structure ? r of the r-degrees containing computably enumerable sets is whether every element not equal to the greatest one is branching (i.e., the meet of two elements strictly above it). For the commonly studied reducibilities, the answer to this question is known except for the case of truth-table (tt) reducibility. In this paper, we answer the question in the tt case by showing that (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. 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  
  4. Peter A. Fejer (1998). Lattice Representations for Computability Theory. Annals of Pure and Applied Logic 94 (1-3):53-74.
    Lattice representations are an important tool for computability theorists when they embed nondistributive lattices into degree-theoretic structures. In this expository paper, we present the basic definitions and results about lattice representations needed by computability theorists. We define lattice representations both from the lattice-theoretic and computability-theoretic points of view, give examples and show the connection between the two types of representations, discuss some of the known theorems on the existence of lattice representations that are of interest to computability theorists, and give (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman (1996). Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices. Journal of Symbolic Logic 61 (3):880-905.
    We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  6. Peter A. Fejer (1989). Embedding Lattices with Top Preserved Below Non‐GL2 Degrees. Mathematical Logic Quarterly 35 (1):3-14.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Klaus Ambos-Spies & Peter A. Fejer (1988). Degree Theoretical Splitting Properties of Recursively Enumerable Sets. Journal of Symbolic Logic 53 (4):1110-1137.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  8. Peter A. Fejer & Richard A. Shore (1988). Infima of Recursively Enumerable Truth Table Degrees. Notre Dame Journal of Formal Logic 29 (3):420-437.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  9. Peter A. Fejer (1983). The Density of the Nonbranching Degrees. Annals of Pure and Applied Logic 24 (2):113-130.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation