Refutable Language Learning with a Neighbor System

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.