On an open problem in classification of languages
Sanjay K. Jain · Journal of Experimental & Theoretical Artificial Intelligence · 2001
Smith, Wiehagen 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 L1,..., Lm+2 such that (1) � i∈{1,2,...,m+1} Li = L, and (2) (L1,..., Lm+2) can be classified from informants. However Smith, Wiehagen and Zeugmann (1997) left open whether a similar result also holds for learning from texts. We show that such a result does not hold for texts.