Using compression to improve edit distance computation I am doing a seminar on a paper titled "Unified Compression-Based Acceleration
of Edit-Distance Computation" that uses straight-line programs to improve edit distance computation. It is a common method to exploit repetitions for ED although I couldn't find the first article that used it and I thought it is important to mention it in the seminar.

Does anybody have a clue what it was?
Thanks!
Crochemore, Landau and Ziv-Ukelson were, I believe, the first to consider (LZ) compression explicitly in this context. As mentioned in the comments above, the earlier technique of Masek and Paterson is also in effect a form of compression. Considering general grammar-compression (SLP) is, I believe, a relatively new idea. Using it for string comparison speedup is original to the paper you cite, although comparing grammar-compressed strings as such has been considered before. You will find references and discussion in the compression chapter of http://arxiv.org/abs/0707.3619 .