**Authors: Ganesh Baliga, John Case, and Sanjay Jain**

**Source: ***Information & Computation* Vol. **152**, No. 1,
1999, 16 - 43.

**Abstract.**
An index for an r.e. class of languages(by definition) is a procedure which
generates a sequence of grammars defining the class. An index for an indexed
family of languages(by definition) is a procedure which generates a
sequence of decision procedures defining the family.
Studied is the metaproblem of synthesizingfrom indices for
r.e. classes and for indexed families of languagesvarious kinds of language
learners for the corresponding classes or families indexed.
Many positive results, as well as some negative results, are presented
regarding the existence of such synthesizers. The negative results essentially
provide lower bounds for the positive results. The proofs of some of the
positive results yield, as pleasant corollaries, subset-principle or
tell-tale style characterizations for the learnability of the corresponding
classes or families indexed. For example, the indexed families of recursive
languages that can be behaviorally correctly identified from positive data are
surprisingly characterized by Angluin's condition 2 (thesubset principle for
circumventing overgeneralization).

©Copyright 1999, Academic Press