Switch to: References

Citations of:

A proof of Beigel's cardinality conjecture

Journal of Symbolic Logic 57 (2):677-681 (1992)

Add citations

You must login to add citations.

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.details 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 (...) Download Export citation Bookmark 4 citations
Computable categoricity and the Ershov hierarchy.Bakhadyr Khoussainov, Frank Stephan & Yue Yang - 2008 - Annals of Pure and Applied Logic 156 (1):86-95.details 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 (...) ordinal α. (shrink) Download Export citation Bookmark 4 citations

1