Learning languages and functions by erasing

Learning by erasing means the process of eliminating potential hypotheses f rom further consideration thereby converging to the least hypothesis never eliminated. This hypothesis must be a solution to the actual learning probl em, The capabilities of learning by erasing are investigated in relation to two factors: the choice of the overall hypothesis space itself and what se ts of hypotheses must or may be erased, These learning capabilities are stu died for two fundamental kinds of objects to be learned, namely languages a nd functions. For learning languages by erasing, the ease of learning index ed families is investigated. A complete picture of all separations and coin cidences of the considered models is derived. Learning by erasing is compar ed with standard models of language learning such as learning in the limit, finite learning and conservative learning. The exact location of these typ es within the hierarchy of the models of learning by erasing is established , Necessary and sufficient conditions for language learning by erasing are presented, For teaming functions by erasing, mainly the case of learning mi nimal programs is studied. Various relationships and differences between th e considered types of function learning by erasing and also to standard fun ction learning are exhibited. In particular, these types are explored in Ko lmogorov numberings that can be vie-wed as natural Godel numberings of the partial recursive functions, Necessary and sufficient conditions fur functi on learning by erasing are derived, (C) 2000 Elsevier Science B.V. All righ ts reserved.