On an open problem in classification of languages

摘要

Smith, Wichagen and Zeugmann (1997) showed an interesting connection between learning with bounded number of mind changes from informants and classification from informant. They showed that if an indexed family of languages L is learnable via informants, using at most m mind changes, then one can partition 2N, the class of all languages, into m + 2 subclasses L_1,..., L_m+2 such that (1) ∪_i∈{1,2.…,m+1} L_i = L, and (2) (L_1 ,…,L_m+2) con be classified from informants. However Smith et al.(1997) left open whether a similar result also holds for learning from texts. We show that such a result does not hold for texts.