38 found
Order:
Disambiguations
Frank Stephan [35]F. Stephan [5]Friedrich Stephan [1]
  1. Van Lambalgen's Theorem and High Degrees.Johanna N. Y. Franklin & Frank Stephan - 2011 - 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 (3 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  2.  12
    Lowness Properties and Approximations of the Jump.Santiago Figueira, André Nies & Frank Stephan - 2008 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   12 citations  
  3.  13
    A Cohesive Set Which is Not High.Carl Jockusch & Frank Stephan - 1993 - 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)  
     
    Export citation  
     
    Bookmark   24 citations  
  4.  22
    Π 1 0 Classes, L R Degrees and Turing Degrees.George Barmpalias, Andrew E. M. Lewis & Frank Stephan - 2008 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   9 citations  
  5.  29
    Schnorr Trivial Sets and Truth-Table Reducibility.Johanna N. Y. Franklin & Frank Stephan - 2010 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   7 citations  
  6.  13
    Kolmogorov–Loveland Randomness and Stochasticity.Wolfgang Merkle, Joseph S. Miller, André Nies, Jan Reimann & Frank Stephan - 2006 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   10 citations  
  7.  6
    Anti-Complex Sets and Reducibilities with Tiny Use.Johanna N. Y. Franklin, Noam Greenberg, Frank Stephan & Guohua Wu - 2013 - Journal of Symbolic Logic 78 (4):1307-1327.
  8.  25
    Graphs Realised by R.E. Equivalence Relations.Alexander Gavruskin, Sanjay Jain, Bakhadyr Khoussainov & Frank Stephan - 2014 - 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 (3 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  9.  16
    Correction to “a Cohesive Set Which is Not High”.Carl Jockusch & Frank Stephan - 1997 - Mathematical Logic Quarterly 43 (4):569-569.
  10.  10
    Computable Categoricity and the Ershov Hierarchy.Bakhadyr Khoussainov, Frank Stephan & Yue Yang - 2008 - 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 (4 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  11.  7
    The Complexity of ODDnA.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy Mcnicholl & Frank Stephan - 2000 - Journal of Symbolic Logic 65 (1):1-18.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  12. Lowness for the Class of Schnorr Random Sets.B. Kjös-Hanssen, A. Nies & F. Stephan - 2005 - Notre Dame Journal of Formal Logic 35 (3):647-657.
     
    Export citation  
     
    Bookmark   5 citations  
  13.  56
    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  
  14.  91
    Higher Kurtz Randomness.Bjørn Kjos-Hanssen, André Nies, Frank Stephan & Liang Yu - 2010 - 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 (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  15.  12
    Effective Search Problems.Martin Kummer & Frank Stephan - 1994 - 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 (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  16.  2
    Reductions Between Types of Numberings.Ian Herbert, Sanjay Jain, Steffen Lempp, Mustafa Manat & Frank Stephan - forthcoming - Annals of Pure and Applied Logic:102716.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  17.  10
    Extremes in the Degrees of Inferability.Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan - 1994 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  18.  23
    Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - 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 (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  19.  7
    Learning Via Queries and Oracles.Frank Stephan - 1998 - 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 (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  20.  50
    Automatic Models of First Order Theories.Pavel Semukhin & Frank Stephan - 2013 - 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 (5 more)  
     
    Export citation  
     
    Bookmark  
  21.  44
    The Complexity of Oddan.Richard Beigel, William Gasarch, Martin Kummer, Georgia Martin, Timothy McNicholl & Frank Stephan - 2000 - 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)  
     
    Export citation  
     
    Bookmark  
  22.  23
    Inductive Inference and Reverse Mathematics.Rupert Hölzl, Sanjay Jain & Frank Stephan - 2016 - Annals of Pure and Applied Logic 167 (12):1242-1266.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  23.  34
    An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - 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 (7 more)  
     
    Export citation  
     
    Bookmark  
  24.  20
    Behavioural Approximations for Restricted Linear Differential Hybrid Automata.Manindra Agrawal, Frank Stephan, P. S. Thiagarajan & Shaofa Yang - 2006 - In O. Stock & M. Schaerf (eds.), Lecture Notes in Computer Science. Springer Verlag. pp. 4-18.
  25.  36
    On the Structures Inside Truth-Table Degrees.Frank Stephan - 2001 - 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 (9 more)  
     
    Export citation  
     
    Bookmark  
  26.  23
    Automata on Ordinals and Automaticity of Linear Orders.Philipp Schlicht & Frank Stephan - 2013 - 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 (6 more)  
     
    Export citation  
     
    Bookmark  
  27.  18
    Weakly Semirecursive Sets and R.E. Orderings.Martin Kummer & Frank Stephan - 1993 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  28.  11
    Topological Aspects of Numberings.Wolfram Menzel & Frank Stephan - 2003 - 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)  
     
    Export citation  
     
    Bookmark  
  29.  10
    Cone Avoidance and Randomness Preservation.Stephen G. Simpson & Frank Stephan - 2015 - Annals of Pure and Applied Logic 166 (6):713-728.
  30.  7
    Covering the Recursive Sets.Bjørn Kjos-Hanssen, Frank Stephan & Sebastiaan A. Terwijn - 2017 - Annals of Pure and Applied Logic 168 (4):804-823.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  31.  10
    Highness, Locally Noncappability and Nonboundings.Frank Stephan & Guohua Wu - 2013 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  32.  6
    Looking for an Analogue of Rice's Theorem in Circuit Complexity Theory.F. Stephan & B. Borchert - 2000 - Mathematical Logic Quarterly 46 (4):489-504.
    Rice's Theorem says that every nontrivia semantic property of programs is undecidable. In this spirit we show the following: Every nontrivia absolute counting property of circuits is UP-hard with respect to polynomial-time Turing reductions. For generators [31] we show a perfect analogue of Rice's Theorem.
    No categories
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  33.  4
    Classes Bounded by Incomplete Sets.Kejia Ho & Frank Stephan - 2002 - 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 (4 more)  
     
    Export citation  
     
    Bookmark  
  34.  4
    Applications of Kolmogorov Complexity to Computable Model Theory.B. Khoussainov, P. Semukhin & F. Stephan - 2007 - Journal of Symbolic Logic 72 (3):1041 - 1054.
    In this paper we answer the following well-known open question in computable model theory. Does there exist a computable not ‮א‬₀-categorical saturated structure with a unique computable isomorphism type? Our answer is affirmative and uses a construction based on Kolmogorov complexity. With a variation of this construction, we also provide an example of an ‮א‬₁-categorical but not ‮א‬₀-categorical saturated $\Sigma _{1}^{0}$ -structure with a unique computable isomorphism type. In addition, using the construction we give an example of an ‮א‬₁-categorical but (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  35. The Importance of $\Pi _1^0$ Classes in Effective Randomness. The Journal of Symbolic Logic, Vol. 75.George Barmpalias, Andrew E. M. Lewis, Keng Meng Ng & Frank Stephan - 2012 - Bulletin of Symbolic Logic 18 (3):409-412.
  36.  7
    Logic Colloquium 2007.F. Delon, U. Kohlenbach, P. Maddy & F. Stephan (eds.) - 2010 - Cambridge University Press.
    The 2007 proceedings from the Annual European Meeting of the Association for Symbolic Logic.
    Direct download  
     
    Export citation  
     
    Bookmark  
  37. M. Gitik Blowing Up Power of a Singular cardinalYwider Gaps 1 D. Pitteloud Algebraic Properties of Rings of Generalized Power Series 39.I. Neeman, D. M. Evans, M. Menni, R. D. Schindler, K. Ho & F. Stephan - 2002 - Annals of Pure and Applied Logic 116 (1):3-15.
  38.  58
    Randomness, Relativization and Turing Degrees.André Nies, Frank Stephan & Sebastiaan A. Terwijn - 2005 - 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 ∅. 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|-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 some results (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   11 citations