Inductive Inference without Overgeneralization from Positive Examples

Abstract

Language learnability is investigated in the Gold paradigm of inductive inference from positive data. Angluin gave a characterization of learnable families in this framework. Here, learnability is studied when the learner obeys certain constraints. These constraints have been suggested by some studies of child language acquisition. Learnable families are characterized for learners with the following types of constraints: (a) conservative, consistent, and responsive, (b) conservative and responsive, (c) conservative and consistent, and (d) conservative. It is shown that the class of learnable families strictly increases going from (a) to (b) and from (b) to (c), while it stays the same going from (c) to (d).