LEARNING DETERMINISTIC EVEN LINEAR LANGUAGES FROM POSITIVE EXAMPLES

We consider the problem of learning deterministic even linear language s from positive examples, We show that, for any nonnegative integer k, the class of LR(k) even linear languages is not learnable from positi ve examples while there is a subclass called LRS(k), which is a natura l subclass of LR(k) in the strong sense, learnable from positive examp les. Our learning algorithm identifies this subclass in the limit with almost linear time in updating conjectures. As a corollary, in terms of even linear grammars, we have a learning algorithm for k-reversible languages that is more efficient than the one proposed by Angluin.