String Extension Learning
Jeffrey Heinz · 2010
This paper defines a collection of functions which define classes of languages, which have the property that they are identifiable in the limit from positive data from a very simple kind of learner. Furthermore these learners are always incremental, maximally consistent, and locally conservative. They are also efficient provided the function itself is efficient. These learners are called string extension learners because components of the grammar are read directly from strings in the language via the defining function. A number of classes of languages in the literature can be described this way including varieties of k-Locally Testable languages (McNaughton and Papert 1971) and k-Piecewise Testable languages (Simon 1975), as well as some classes not discussed in the literature, such as the k-Piecewise Testable languages in the Strict Sense. Potential applications of string extension learning exist for models of natural languages, particularly phonotactics, aspects of cognition and natural language processing.