Greedy Grammar Induction with Indirect Negative Evidence
Joseph Potashnik
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.