SIMPLE FLAT LANGUAGES: A LEARNABLE CLASS IN THE LIMIT FROM POSITIVE DATA
OKADOME TAKESI · International Journal of Foundations of Computer Science · 1999
The class of simple flat languages defined here is shonw to be learnable in the limit from positive data. In particular, its subclass named k-consecutive, which covers a part of the class of context-sensitive languages not belonging to the class of context-free languages, is polynomial-time learnable in the limit from positive data. The class of "disjunct" unions of simple flat languages is a nontrivial example which is learnable in the limit from positive data, but does not have Wright's finite elasticity. The learning algorithm presented here for identifying the subclasses of flat languages consists essentially of identifying an arithmetic progression in the limit from positive examples using Euclidean algorithm of mutual division.