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