27 found
Sort by:
  1. Philipp Schlicht & Frank Stephan (2013). Automata on Ordinals and Automaticity of Linear Orders. Annals of Pure and Applied Logic 164 (5):523-527.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  2. Pavel Semukhin & Frank Stephan (2013). Automatic Models of First Order Theories. Annals of Pure and Applied Logic 164 (9):837-854.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Frank Stephan & Guohua Wu (2013). Highness, Locally Noncappability and Nonboundings. Annals of Pure and Applied Logic 164 (5):511-522.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Frank Stephan & Jason Teutsch (2012). An Incomplete Set of Shortest Descriptions. Journal of Symbolic Logic 77 (1):291-307.
    The truth-table degree of the set of shortest programs remains an outstanding problem in recursion theory. We examine two related sets, the set of shortest descriptions and the set of domain-random strings, and show that the truth-table degrees of these sets depend on the underlying acceptable numbering. We achieve some additional properties for the truth-table incomplete versions of these sets, namely retraceability and approximability. We give priority-free constructions of bounded truth-table chains and bounded truth-table antichains inside the truth-table complete degree (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Johanna N. Y. Franklin & Frank Stephan (2010). Schnorr Trivial Sets and Truth-Table Reducibility. Journal of Symbolic Logic 75 (2):501-521.
    We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Johanna N. Y. Franklin & Frank Stephan (2010). Van Lambalgen's Theorem and High Degrees. Notre Dame Journal of Formal Logic 52 (2):173-185.
    We show that van Lambalgen's Theorem fails with respect to recursive randomness and Schnorr randomness for some real in every high degree and provide a full characterization of the Turing degrees for which van Lambalgen's Theorem can fail with respect to Kurtz randomness. However, we also show that there is a recursively random real that is not Martin-Löf random for which van Lambalgen's Theorem holds with respect to recursive randomness.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu (2010). Higher Kurtz Randomness. Annals of Pure and Applied Logic 161 (10):1280-1290.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  8. George Barmpalias, Andrew E. M. Lewis & Frank Stephan (2008). Classes, Degrees and Turing Degrees. Annals of Pure and Applied Logic 156 (1):21-38.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. George Barmpalias, Andrew Em Lewis & Frank Stephan (2008). Http://Ars. Els-Cdn. Com/Content/Image/Http://Origin-Ars. Els-Cdn. Com/Content/Image/1-S2. 0-S0168007208000821-Si1. Gif"/> Classes, LR Degrees and Turing Degrees. [REVIEW] Annals of Pure and Applied Logic 156 (1):21-38.
    Direct download  
     
    My bibliography  
     
    Export citation  
  10. Santiago Figueira, André Nies & Frank Stephan (2008). Lowness Properties and Approximations of the Jump. Annals of Pure and Applied Logic 152 (1):51-66.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  11. Bakhadyr Khoussainov, Frank Stephan & Yue Yang (2008). Computable Categoricity and the Ershov Hierarchy. Annals of Pure and Applied Logic 156 (1):86-95.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  12. Frank Stephan & Jason Teutsch (2008). Immunity and Hyperimmunity for Sets of Minimal Indices. Notre Dame Journal of Formal Logic 49 (2):107-125.
    We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three minimal index sets located (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  13. Manindra Agrawal, Frank Stephan, P. S. Thiagarajan & Shaofa Yang (2006). Behavioural Approximations for Restricted Linear Differential Hybrid Automata. In O. Stock & M. Schaerf (eds.), Lecture Notes in Computer Science. Springer-Verlag. 4-18.
    No categories
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  14. Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, Luc Longpré, Andrej Muchnik, Frank Stephan & Leen Torenvliet (2006). Enumerations of the Kolmogorov Function. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  15. Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan (2006). Kolmogorov–Loveland Randomness and Stochasticity. Annals of Pure and Applied Logic 138 (1):183-210.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  16. André Nies, Frank Stephan & Sebastiaan A. Terwijn (2005). Randomness, Relativization and Turing Degrees. Journal of Symbolic Logic 70 (2):515 - 535.
    We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to θ(n−1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ |x| − c. The 'only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  17. Wolfram Menzel & Frank Stephan (2003). Topological Aspects of Numberings. Mathematical Logic Quarterly 49 (2):129-149.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Kejia Ho & Frank Stephan (2002). Classes Bounded by Incomplete Sets. Annals of Pure and Applied Logic 116 (1-3):273-295.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  19. Frank Stephan (2001). On One-Sided Versus Two-Sided Classification. Archive for Mathematical Logic 40 (7):489-513.
    One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ0 2 classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure.There (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  20. Frank Stephan (2001). On the Structures Inside Truth-Table Degrees. Journal of Symbolic Logic 66 (2):731-770.
    The following theorems on the structure inside nonrecursive truth-table degrees are established: Dëgtev's result that the number of bounded truth-table degrees inside a truth-table degree is at least two is improved by showing that this number is infinite. There are even infinite chains and antichains of bounded truth-table degrees inside every truth-table degree. The latter implies an affirmative answer to the following question of Jockusch: does every truth-table degree contain an infinite antichain of many-one degrees? Some but not all truth-table (...)
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  21. 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  
  22. Frank Stephan (1998). Learning Via Queries and Oracles. Annals of Pure and Applied Logic 94 (1-3):273-296.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Carl Jockusch & Frank Stephan (1997). Correction to “a Cohesive Set Which is Not High”. Mathematical Logic Quarterly 43 (4):569-569.
    No categories
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  24. 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  
  25. 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  
  26. Carl Jockusch & Frank Stephan (1993). A Cohesive Set Which is Not High. Mathematical Logic Quarterly 39 (1):515-530.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  27. 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