Grammatical inference refers to the process of learning grammars and languages from data. In literature, it refers to automata induction, grammar induction, and automatic language acquisition. There are applications for machine learning in syntactic pattern recognition, adaptive intelligent agents, diagnosis, computational biology, systems modeling, prediction, natural language acquisition, data mining, and knowledge discovery. This paper does not go into the details and mechanics of implementing grammatical inference, and in this sense it is not the paper on machine learning that one would expect. Instead, it is well written, mathematically impeccable, algebraic, theoretical, and, ultimately, of great importance.
It presents and discusses a class of languages called V*LI, where V is a syntactic semigroup, and LI is the variety of locally trivial semigroups. It is a general class that contains some languages that have previously been given significant research attention, such as locally testable, reversible, and dot-depth one languages. Given the sequences of words of a language or their complete presentation (positive data), the methods given in this paper unify the existing inference algorithms. This procedure generalizes the approach and is expected to be applied in related domains. As it is illustrated with figures that are complementary to the text, this formalism-packed paper is well worth the effort required to cross-reference definitions and understand the implications of the theory discussed.