This research paper is devoted to a comparison between the theoretical capabilities of query learning models, in the sense of Angluin [1], and those of models of Gold-style language learning [2], in the frame of indexable classes of recursive languages. The question is: does a given language L belong to the class C?

A query learner is an algorithmic device (completed by an “oracle”) that, using previous replies, computes a new query, or picks the required language in the class (and halts). Allowed queries are of these types: membership (Is a string w in the language?), equivalence (Is the language equivalent to a given one?), superset (Is the language included in a given one?), and subset (Does the language includes a given one?). In models of Gold-style language learning, one indexes the string in L by integers; for any sequence w₀,w₁,..,w_n of strings in L, the algorithmic device returns the address of a possible target in C. If, in scrutinizing the successive strings, one gets a stabilized address, the language belongs to the class.

For each model, one deals with the set of classes in which any language may be recognized, and with various analog ones (by example, one may discard one type of query). The core of the paper is paragraph 3, where Theorems 3 and 4 give some positive and negative results about the mutual inclusions of the previous sets, the models of language learning being the more “powerful” (but not the more manageable). In paragraph 4, the authors suggest an eventual solution to a major drawback of query models learning: a subclass of a recognizable one may be unrecognizable. They study the new capabilities gained by the immersion of the class in a superclass. The aim is to show that learners in Gold style may be replaced by the more flexible query learners. Finally, an opportune summary collects the most important results in a diagram.