The synthesis of language learners

An index for an r.e. class of languages (by definition) is a procedure whic h generates a sequence of grammars defining the class, An index for an inde xed family of languages (by definition) is a procedure which generates a se quence of decision procedures defining the family. Studied is the metaprobl em of synthesizing from indices for r.e. classes and for indexed families o f languages various kinds of language learners for the corresponding classe s or families indexed. Many positive results, as well as some negative resu lts, are presented regarding the existence of such synthesizers. The negati ve results essentially provide lower bounds for the positive results. The p roofs of some of the positive results yield, as pleasant corollaries, subse t-principle or tell-tale style characterizations for the learnability of th e corresponding classes or families indexed. For example, the indexed famil ies of recursive languages that can be behaviorally correctly identified fr om positive data are surprisingly characterized by Angluin's condition 2 (t he subset principle for circumventing overgeneralization). (C) 1999 Academi c Press.