29 found
Sort by:
  1. Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan (2014). Graphs Realised by R.E. Equivalence Relations. Annals of Pure and Applied Logic 165 (7-8):1263-1290.
    We investigate dependence of recursively enumerable graphs on the equality relation given by a specific r.e. equivalence relation on ω. In particular we compare r.e. equivalence relations in terms of graphs they permit to represent. This defines partially ordered sets that depend on classes of graphs under consideration. We investigate some algebraic properties of these partially ordered sets. For instance, we show that some of these partial ordered sets possess atoms, minimal and maximal elements. We also fully describe the isomorphism (...)
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Philipp Schlicht & Frank Stephan (2013). Automata on Ordinals and Automaticity of Linear Orders. Annals of Pure and Applied Logic 164 (5):523-527.
    We investigate structures recognizable by finite state automata with an input tape of length a limit ordinal. At limits, the set of states which appear unboundedly often before the limit are mapped to a limit state. We describe a method for proving non-automaticity and apply this to determine the optimal bounds for the ranks of linear orders recognized by such automata.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  3. Pavel Semukhin & Frank Stephan (2013). Automatic Models of First Order Theories. Annals of Pure and Applied Logic 164 (9):837-854.
    Khoussainov and Nerode [14] posed various open questions on model-theoretic properties of automatic structures. In this work we answer some of these questions by showing the following results: There is an uncountably categorical but not countably categorical theory for which only the prime model is automatic; There are complete theories with exactly 3,4,5,…3,4,5,… countable models, respectively, and every countable model is automatic; There is a complete theory for which exactly 2 models have an automatic presentation; If LOGSPACE=PLOGSPACE=P then there is (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  4. Frank Stephan & Guohua Wu (2013). Highness, Locally Noncappability and Nonboundings. Annals of Pure and Applied Logic 164 (5):511-522.
    In this paper, we improve a result of Seetapun and prove that above any nonzero, incomplete recursively enumerable degree a, there is a high2 r.e. degree c>ac>a witnessing that a is locally noncappable . Theorem 1.1 provides a scheme of obtaining high2 nonboundings , as all known high2 nonboundings, such as high2 degrees bounding no minimal pairs, high2 plus-cuppings, etc.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  5. George Barmpalias, Andrew E. M. Lewis, Keng Meng Ng & Frank Stephan (2012). The Importance of $\Pi _1^0$ Classes in Effective Randomness. The Journal of Symbolic Logic, Vol. 75. Bulletin of Symbolic Logic 18 (3):409-412.
     
    My bibliography  
     
    Export citation  
  6. 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  
  7. 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  
  8. 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  
  9. Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu (2010). Higher Kurtz Randomness. Annals of Pure and Applied Logic 161 (10):1280-1290.
    A real x is -Kurtz random if it is in no closed null set . We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  10. George Barmpalias, Andrew E. M. Lewis & Frank Stephan (2008). Classes, Degrees and Turing Degrees. Annals of Pure and Applied Logic 156 (1):21-38.
    We say that A≤LRB if every B-random set is A-random with respect to Martin–Löf randomness. We study this relation and its interactions with Turing reducibility, classes, hyperimmunity and other recursion theoretic notions.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  11. 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  
  12. Santiago Figueira, André Nies & Frank Stephan (2008). Lowness Properties and Approximations of the Jump. Annals of Pure and Applied Logic 152 (1):51-66.
    We study and compare two combinatorial lowness notions: strong jump-traceability and well-approximability of the jump, by strengthening the notion of jump-traceability and super-lowness for sets of natural numbers. A computable non-decreasing unbounded function h is called an order function. Informally, a set A is strongly jump-traceable if for each order function h, for each input e one may effectively enumerate a set Te of possible values for the jump JA, and the number of values enumerated is at most h. A′ (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  13. Bakhadyr Khoussainov, Frank Stephan & Yue Yang (2008). Computable Categoricity and the Ershov Hierarchy. Annals of Pure and Applied Logic 156 (1):86-95.
    In this paper, the notions of Fα-categorical and Gα-categorical structures are introduced by choosing the isomorphism such that the function itself or its graph sits on the α-th level of the Ershov hierarchy, respectively. Separations obtained by natural graphs which are the disjoint unions of countably many finite graphs. Furthermore, for size-bounded graphs, an easy criterion is given to say when it is computable-categorical and when it is only G2-categorical; in the latter case it is not Fα-categorical for any recursive (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  14. 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  
  15. 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  
  16. 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  
  17. 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.
    An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our first (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. 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  
  19. Wolfram Menzel & Frank Stephan (2003). Topological Aspects of Numberings. Mathematical Logic Quarterly 49 (2):129-149.
    We investigate connections between the syntactic and semantic distance of programs on an abstract, recursion theoretic level. For a certain rather restrictive notion of interdependency of the two kinds of distances, there remain only few and “unnatural” numberings allowing such close relationship. Weakening the requirements leads to the discovery of universal metrics such that for an arbitrary recursively enumerable family of functions a numbering compatible with such a metric can uniformly be constructed. We conclude our considerations with some implications on (...)
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  20. Kejia Ho & Frank Stephan (2002). Classes Bounded by Incomplete Sets. Annals of Pure and Applied Logic 116 (1-3):273-295.
    We study connections between strong reducibilities and properties of computably enumerable sets such as simplicity. We say that a class of computably enumerable sets bounded iff there is an m-incomplete computably enumerable set A such that every set in is m-reducible to A. For example, we show that the class of effectively simple sets is bounded; but the class of maximal sets is not. Furthermore, the class of computably enumerable sets Turing reducible to a computably enumerable set B is bounded (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  21. 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  
  22. 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  
  23. 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  
  24. Frank Stephan (1998). Learning Via Queries and Oracles. Annals of Pure and Applied Logic 94 (1-3):273-296.
    Inductive inference considers two types of queries: Queries to a teacher about the function to be learned and queries to a non-recursive oracle. This paper combines these two types — it considers three basic models of queries to a teacher (QEX[Succ], QEX[ The results for each of these three models of query-inference are the same: If an oracle is omniscient for query-inference then it is already omniscient for EX. There is an oracle of trivial EX-degree, which allows nontrivial query-inference. Furthermore, (...)
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  25. 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  
  26. 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.
    Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...)
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  27. Martin Kummer & Frank Stephan (1994). Effective Search Problems. Mathematical Logic Quarterly 40 (2):224-236.
    The task of computing a function F with the help of an oracle X can be viewed as a search problem where the cost measure is the number of queries to X. We ask for the minimal number that can be achieved by a suitable choice of X and call this quantity the query complexity of F. This concept is suggested by earlier work of Beigel, Gasarch, Gill, and Owings on “Bounded query classes”. We introduce a fault tolerant version and (...)
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  28. Carl Jockusch & Frank Stephan (1993). A Cohesive Set Which is Not High. Mathematical Logic Quarterly 39 (1):515-530.
    We study the degrees of unsolvability of sets which are cohesive . We answer a question raised by the first author in 1972 by showing that there is a cohesive set A whose degree a satisfies a' = 0″ and hence is not high. We characterize the jumps of the degrees of r-cohesive sets, and we show that the degrees of r-cohesive sets coincide with those of the cohesive sets. We obtain analogous results for strongly hyperimmune and strongly hyperhyperimmune sets (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  29. Martin Kummer & Frank Stephan (1993). Weakly Semirecursive Sets and R.E. Orderings. Annals of Pure and Applied Logic 60 (2):133-150.
    Weakly semirecursive sets have been introduced by Jockusch and Owings . In the present paper their investigation is pushed forward by utilizing r.e. partial orderings, which turn out to be instrumental for the study of degrees of subclasses of weakly semirecursive sets.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation