@proceedings { ,
	title = {Choosing Word Occurrences for the Smallest Grammar Problem},
	year = {2010},
	publisher = {Springer},
	abstract = {The smallest grammar problem - namely, finding a smallest context-free grammar that generates exactly one sequence - is of practical and theoretical importance in fields such as Kolmogorov complexity, data compression and pattern discovery.  We propose to focus on the choice of the occurrences to be rewritten by non-terminals. We extend classical offline algorithms by introducing a global optimization of this choice at each step of the algorithm. This approach allows us to define the search space of a smallest grammar by separating the choice of the non-terminals and the choice of their occurrences. We propose a second algorithm that performs a broader exploration by allowing the removal of useless words that were chosen previously. Experiments on a classical benchmark show that our algorithms consistently find smaller grammars then state-of-the-art algorithms.
},
       pages = { 154-165 },
	author = { Rafael Carrascosa and Fran\c{c}ois Coste and Matthias Gall\'e and Gabriel Infante-Lopez}
}