11 found
Peter A. Fejer [10]Peter Fejer [2]
  1.  29
    The Density of the Nonbranching Degrees.Peter A. Fejer - 1983 - Annals of Pure and Applied Logic 24 (2):113-130.
  2.  29
    Degree Theoretical Splitting Properties of Recursively Enumerable Sets.Klaus Ambos-Spies & Peter A. Fejer - 1988 - Journal of Symbolic Logic 53 (4):1110-1137.
    A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is natural to study the relation between the degrees of (...)
    Direct download (8 more)  
    Export citation  
    Bookmark   7 citations  
  3.  67
    Enumerations of the Kolmogorov Function.Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet - 2006 - Journal of Symbolic Logic 71 (2):501 - 528.
    A recursive enumerator for a function h is an algorithm f which enumerates for an input x finitely many elements including h(x), f is a k(n)-enumerator if for every input x of length n, h(x) is among the first k(n) elements enumerated by f. If there is a k(n)-enumerator for h then h is called k(n)-enumerable. We also consider enumerators which are only A-recursive for some oracle A. We determine exactly how hard it is to enumerate the Kolmogorov function, which (...)
    Direct download (7 more)  
    Export citation  
    Bookmark   3 citations  
  4.  53
    Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - 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 (10 more)  
    Export citation  
    Bookmark   3 citations  
  5.  13
    Embeddings of N5 and the Contiguous Degrees.Klaus Ambos-Spies & Peter A. Fejer - 2001 - 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 (5 more)  
    Export citation  
    Bookmark   3 citations  
  6.  24
    Every Incomplete Computably Enumerable Truth-Table Degree is Branching.Peter A. Fejer & Richard A. Shore - 2001 - 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 (5 more)  
    Export citation  
  7.  11
    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  
  8.  10
    Lattice Representations for Computability Theory.Peter A. Fejer - 1998 - 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 (4 more)  
    Export citation  
  9.  24
    Embedding Lattices with Top Preserved Below Non-GL2 Degrees.Peter A. Fejer - 1989 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 35 (1):3-14.
  10.  19
    Embedding Lattices with Top Preserved Below Non‐GL2 Degrees.Peter A. Fejer - 1989 - Mathematical Logic Quarterly 35 (1):3-14.
  11.  6
    Infima of Recursively Enumerable Truth Table Degrees.Peter A. Fejer & Richard A. Shore - 1988 - Notre Dame Journal of Formal Logic 29 (3):420-437.