Refutable Language Learning with a Neighbor System Authors: Yasuhito Mukouchi and Masako Sato. Source: Lecture Notes in Artificial Intelligence Vol. 2225, 2001, 267 - 282. Abstract. We consider inductive language learning and machine discovery from examples with some errors. In the present paper, the error or incorrectness we consider is the one described uniformly in terms of a distance over strings. Firstly, we introduce a notion of a recursively generable distance over strings, and for a language L, we define a k-neighbor language L' as a language obtained from L by (i) adding some strings not in L each of which is at most k distant from some string in L and by (ii) deleting some strings in L each of which is at most k distant from some string not in L. Then we define a k-neighbor system of a base language class as the collection of k-neighbor languages of languages in the class, and adopt it as a hypothesis space. We give formal definitions of k-neighbor (refutable) inferability, and discuss necessary and sufficient conditions on such kinds of inference. ©Copyright 2001 Springer