  The Smallest Grammar Problem -- the problem of finding the smallest
context-free grammar that generates exactly one given sequence -- has never
been successfully applied to grammatical inference. We investigate the reasons
and propose an extended formulation that seeks to minimize non-recursive
grammars, instead of straight-line programs. In addition, we provide very
efficient algorithms that approximate the minimization problem of this class of
grammars. Our empirical evaluation shows that we are able to find smaller
models than the current best approximations to the Smallest Grammar Problem on
standard benchmarks, and that the inferred rules capture much better the
syntactic structure of natural language.
