Greedy Grammar Induction with Indirect Negative Evidence

This paper offers a fresh look at the pumping lemma constant as an upper bound for the finite structural information of a Context Free Grammar. An objective function based on indirect negative evidence considers the occurrences, and non-occurrences, of a finite number of trees, encountered after a sufficiently long non-adversial input presentation. This objective function has optimal substructure in the hypotheses space, giving rise to a greedy search learner. With this learner, a range of classes of Context Free Languages is shown to be learnable (identifiable in the limit) on an otherwise intractable hypotheses space.