Switch to: References

Citations of:

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

Annals of Pure and Applied Logic 66 (3):231-276 (1994)

Add citations

You must login to add citations.

Learning via queries and oracles.Frank Stephan - 1998 - Annals of Pure and Applied Logic 94 (1-3):273-296.details 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, (...) Download Export citation Bookmark 3 citations
Approximation methods in inductive inference.William R. Moser - 1998 - Annals of Pure and Applied Logic 93 (1-3):217-253.details In many areas of scientific inquiry, the phenomena under investigation are viewed as functions on the real numbers. Since observational precision is limited, it makes sense to view these phenomena as bounded functions on the rationals. One may translate the basic notions of recursion theory into this framework by first interpreting a partial recursive function as a function on Q. The standard notions of inductive inference carry over as well, with no change in the theory. When considering the class of (...) Download Export citation Bookmark 1 citation
The complexity of learning SUBSEQ(A).Stephen Fenner, William Gasarch & Brian Postow - 2009 - Journal of Symbolic Logic 74 (3):939-975.details Higman essentially showed that if A is any language then SUBSEQ(A) is regular, where SUBSEQ(A) is the language of all subsequences of strings in A. Let s1, s2, s3, . . . be the standard lexicographic enumeration of all strings over some finite alphabet. We consider the following inductive inference problem: given A(s1), A(s2), A(s3), . . . . learn, in the limit, a DFA for SUBSEQU). We consider this model of learning and the variants of it that are usually (...) Download Export citation Bookmark
Teachers, Learners, and Oracles.Achilles Beros & Colin de la Higuera - 2019 - Notre Dame Journal of Formal Logic 60 (1):13-26.details 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

1