LANGUAGE-LEARNING WITHOUT OVERGENERALIZATION

Language learnability is investigated in the Gold paradigm of inductiv e inference from positive data. Angluin gave a characterization of lea rnable families in this framework. Here, learnability of families of r ecursive languages is studied when the learner obeys certain natural c onstraints. Exactly learnable families are characterized for prudent l earners with the following types of constraints: (0) conservative, (1) conservative and consistent, (2) conservative and responsive, and (3) conservative, consistent and responsive. The class of learnable famil ies is shown to strictly increase going from (3) to (2) and from (2) t o (1), while it stays the same going from (1) to (0). It is also shown that, when exactness is not required, prudence, consistency and respo nsiveness, even together, do not restrict the power of conservative le arners.