Switch to: Citations

Add references

You must login to add references.
  1. 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 (...)
    Download  
     
    Export citation  
     
    Bookmark   4 citations  
  • Teachers, Learners, and Oracles.Achilles Beros & Colin de la Higuera - 2019 - Notre Dame Journal of Formal Logic 60 (1):13-26.
    We exhibit a family of computably enumerable sets which can be learned within polynomial resource bounds given access only to a teacher but which requires exponential resources to be learned given access only to a membership oracle. In general, we compare the families that can be learned with and without teachers and oracles for four measures of efficient learning.
    Download  
     
    Export citation  
     
    Bookmark   1 citation