Monotonic Language Learning

Abstract

Learnability of families of recursive languages from positive data is studied in the Gold paradigm of inductive inference, where the learner obeys certain constraints motivated by work in inductive reasoning. Previously, various notions of monotonicity have been defined in the context of language learning. These constraints require that the learner's guess monotonically ‘improves’ with regard to the target language. In this paper, the ideas from inductive reasoning are instantiated in alternative ways. Links are established between the various new constraints both among themselves as well as with other well-known constraints, such as conservativeness. Exactly learnable families are characterized for prudent learners which obey various combinations of these constraints. Applications of these characterizations are also shown.