13 found
Sort by:
  1. Martin Kummer & Marcus Schaefer (2007). Cuppability of Simple and Hypersimple Sets. Notre Dame Journal of Formal Logic 48 (3):349-369.
    An incomplete degree is cuppable if it can be joined by an incomplete degree to a complete degree. For sets fulfilling some type of simplicity property one can now ask whether these sets are cuppable with respect to a certain type of reducibilities. Several such results are known. In this paper we settle all the remaining cases for the standard notions of simplicity and all the main strong reducibilities.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  2. Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan (2000). The Complexity of Oddan. Journal of Symbolic Logic 65 (1):1 - 18.
    For a fixed set A, the number of queries to A needed in order to decide a set S is a measure of S's complexity. We consider the complexity of certain sets defined in terms of A: $ODD^A_n = \{(x_1, \dots ,x_n): {\tt\#}^A_n(x_1, \dots, x_n) \text{is odd}\}$ and, for m ≥ 2, $\text{MOD}m^A_n = \{(x_1, \dots ,x_n):{\tt\#}^A_n(x_1, \dots ,x_n) \not\equiv 0 (\text{mod} m)\},$ where ${\tt\#}^A_n(x_1, \dots ,x_n) = A(x_1)+\cdots+A(x_n)$ . (We identify A(x) with χ A (x), where χ A is (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  3. Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan (1994). Extremes in the Degrees of Inferability. Annals of Pure and Applied Logic 66 (3):231-276.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Eberhard Herrmann & Martin Kummer (1994). Diagonals and D-Maximal Sets. Journal of Symbolic Logic 59 (1):60-72.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  5. Eberhard Herrmann & Martin Kummer (1994). Diagonals and $Mathscr{D}$-Maximal Sets. Journal of Symbolic Logic 59 (1):60-72.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  6. Martin Kummer & Frank Stephan (1994). Effective Search Problems. Mathematical Logic Quarterly 40 (2):224-236.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Martin Kummer & Frank Stephan (1993). Weakly Semirecursive Sets and R.E. Orderings. Annals of Pure and Applied Logic 60 (2):133-150.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  8. Valentina Harizanov, Martin Kummer & Jim Owings (1992). Frequency Computations and the Cardinality Theorem. Journal of Symbolic Logic 57 (2):682-687.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  9. Martin Kummer (1992). A Proof of Beigel's Cardinality Conjecture. Journal of Symbolic Logic 57 (2):677-681.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  10. Martin Kummer (1991). Diagonals and Semihyperhypersimple Sets. Journal of Symbolic Logic 56 (3):1068-1074.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  11. Martin Kummer (1990). Some Applications of Computable One-One Numberings. Archive for Mathematical Logic 30 (4):219-230.
    We present a simple proof of a Theorem of Khutoretskij on the number of incomparable one-one numberings of an r.e. family of r.e. sets. The proof directly generalizes to effective domains. In the second part, applying a Theorem of Goncharov, we show that for anyk≧ there exist total recursive functions having exactlyk recursive isomorphism classes. Using a Theorem of Selivanov, it is shown that a certain notion of computability via gödelization is different from Lacombe's notion ofV-recursiveness. Finally, we discuss the (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Martin Kummer (1989). A Note on Direct Sums of Friedbergnumberings. Journal of Symbolic Logic 54 (3):1009-1010.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  13. Martin Kummer (1988). The Length Problem for Co‐R.E. Sets. Mathematical Logic Quarterly 34 (3):277-282.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation