Refutable language learning with a neighbor system

✍ Scribed by Yasuhito Mukouchi; Masako Sato

• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 239 KB
• Volume: 298
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(02)00420-6

✦ Synopsis

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 deÿne 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 deÿne 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 deÿnitions of k-neighbor (refutable) inferability, and discuss necessary and su cient conditions on such kinds of inference.

Finally, as a concrete class inferable in the sense we introduced, we consider a language class deÿnable by elementary formal systems (EFSs for short). As a main result, we show that the language class deÿnable by the so-called length-bounded EFSs with at most n axioms is refutable and inferable from complete examples.