Learning Concatenations of Locally Testable Languages from Positive Data

Abstract

This paper introduces the class of concatenations of locally testable languages and its subclasses, and presents some results on the learnability of the classes from positive data. We first establish several relationships among the language classes introduced, and give a sufficient condition for a concatenation operation to preserve finite elasticity of a language class C . Then we show that, for each k , the class CLT ^≤ k, a subclass of concatenations of locally testable languages, is identifiable in the limit from positive data. Further, we introduce a notion of local parsability , and define a class ( k, l)-CLTS , which is a subclass of the class of concatenations of strictly locally testable languages. Then, for each k, l ≥ 1, (k, l)-CLTS is proved to be identifiable in the limit from positive data using reversible automata with the conjectures updated in polynomial time. Some possible applications of this result are also briefly discussed.