A. Aggarwal, M. M. Klawe, S. Moran, P. Shor, and R. Wilber, Geometric applications of a matrix-searching algorithm, Algorithmica, vol.9, issue.1-4, pp.195-208, 1987.
DOI : 10.1007/BF01840359

A. Amir, G. Benson, and M. Farach, Let Sleeping Files Lie: Pattern Matching in Z-Compressed Files, Journal of Computer and System Sciences, vol.52, issue.2, pp.299-307, 1996.
DOI : 10.1006/jcss.1996.0023

A. Amir, G. M. Landau, and D. Sokol, Inplace 2D matching in compressed images, Proc. of the 14th annual ACM-SIAM Symposium On Discrete AlgorithmsSODA), pp.853-862, 2003.
DOI : 10.1016/S0196-6774(03)00088-9

A. Apostolico, M. J. Atallah, L. L. Larmore, and S. Mcfaddin, Efficient Parallel Algorithms for String Editing and Related Problems, SIAM Journal on Computing, vol.19, issue.5, pp.968-988, 1990.
DOI : 10.1137/0219066

A. Apostolico, G. M. Landau, and S. Skiena, Matching for Run-Length Encoded Strings, Journal of Complexity, vol.15, issue.1, pp.4-16, 1999.
DOI : 10.1006/jcom.1998.0493

O. Arbell, G. M. Landau, and J. Mitchell, Edit distance of run-length encoded strings, Information Processing Letters, vol.83, issue.6, pp.307-314, 2001.
DOI : 10.1016/S0020-0190(02)00215-6

P. Bille and M. Farach-colton, Fast and compact regular expression matching, Theoretical Computer Science, vol.409, issue.3, 2005.
DOI : 10.1016/j.tcs.2008.08.042

H. Bunke and J. Csirik, An improved algorithm for computing the edit distance of run-length coded strings, Information Processing Letters, vol.54, issue.2, pp.93-96, 1995.
DOI : 10.1016/0020-0190(95)00005-W

P. Cégielski, I. Guessarian, Y. Lifshits, and Y. Matiyasevich, Window Subsequence Problems for Compressed Texts, Proc. of the 1st symp. on Computer Science in Russia (CSR), pp.127-136, 2006.
DOI : 10.1007/11753728_15

M. Crochemore, G. M. Landau, and M. Ziv-ukelson, A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices, SIAM Journal on Computing, vol.32, issue.6, pp.1654-1673, 2003.
DOI : 10.1137/S0097539702402007
URL : https://hal.archives-ouvertes.fr/hal-00619573

D. Gusfield, Algorithms on Strings, Trees, and Sequences, Computer Science and Computational Biology, 1997.
DOI : 10.1017/CBO9780511574931

J. Karkkainen, G. Navarro, and E. Ukkonen, Approximate String Matching over Ziv???Lempel Compressed Text, Proc. of the 11th symposium on Combinatorial Pattern Matching (CPM), pp.195-209, 2000.
DOI : 10.1007/3-540-45123-4_18

J. Karkkainen and E. Ukkonen, Lempel-Ziv parsing and sublinear-size index structures for string matching, Proc. of the 3rd South American Workshop on String Processing (WSP), pp.141-155, 1996.

M. Karpinski, W. Rytter, and A. Shinohara, Pattern-matching for strings with short descriptions, Proc. of the 6th symposium on Combinatorial Pattern Matching (CPM), pp.205-214, 1995.
DOI : 10.1007/3-540-60044-2_44

E. Lehman and A. Shelat, Approximation algorithms for grammar-based compression, Proc. of the 13th annual ACM-SIAM Symposium On Discrete AlgorithmsSODA), pp.205-212, 2002.

V. I. Levenshtein, Binary codes capable of correcting deletions, insertions and reversals, Soviet Physics Doklady, vol.10, issue.8, pp.707-710, 1966.

Y. Lifshits, Processing Compressed Texts: A Tractability Border, Proc. of the 18th symposium on Combinatorial Pattern Matching (CPM), pp.228-240, 2007.
DOI : 10.1007/978-3-540-73437-6_24

Y. Lifshits and M. Lohrey, Querying and Embedding Compressed Texts, Proc. of the 31st international symposium on Mathematical Foundations of Computer Science (MFCS), pp.681-692, 2006.
DOI : 10.1007/11821069_59

V. Makinen, G. Navarro, and E. Ukkonen, Approximate matching of run-length compressed strings, Proc. of the 12th Symposium On Combinatorial Pattern Matching (CPM), pp.1-13, 1999.

U. Manber, A text compression scheme that allows fast searching directly in the compressed file, Proc of the 5th Symposium On Combinatorial Pattern Matching (CPM), pp.31-49, 1994.

W. J. Masek and M. S. Paterson, A faster algorithm computing string edit distances, Journal of Computer and System Sciences, vol.20, issue.1, 1980.
DOI : 10.1016/0022-0000(80)90002-1

M. Miyazaki, A. Shinohara, and M. Takeda, An improved pattern matching algorithm for strings in terms of straight-line programs, Proc. of the 8th symposium on Combinatorial Pattern Matching (CPM), pp.1-11, 1997.
DOI : 10.1007/3-540-63220-4_45

S. Mozes, O. Weimann, and M. Ziv-ukelson, Speeding Up HMM Decoding and Training by Exploiting Sequence Repetitions, Proc. of the 18th symposium on Combinatorial Pattern Matching (CPM), pp.4-15, 2007.
DOI : 10.1007/978-3-540-73437-6_4

G. Navarro, T. Kida, M. Takeda, A. Shinohara, and S. Arikawa, Faster approximate string matching over compressed text, Proceedings DCC 2001. Data Compression Conference, pp.459-468, 2001.
DOI : 10.1109/DCC.2001.917177

W. Rytter, Application of Lempel???Ziv factorization to the approximation of grammar-based compression, Theoretical Computer Science, vol.302, issue.1-3, pp.211-222, 2003.
DOI : 10.1016/S0304-3975(02)00777-6

J. P. Schmidt, All Highest Scoring Paths in Weighted Grid Graphs and Their Application to Finding All Approximate Repeats in Strings, SIAM Journal on Computing, vol.27, issue.4, pp.972-992, 1998.
DOI : 10.1137/S0097539795288489

Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara et al., Byte Pair encoding: A text compression scheme that accelerates pattern matching, 1999.

Y. Shibata, T. Kida, S. Fukamachi, M. Takeda, A. Shinohara et al., Speeding Up Pattern Matching by Text Compression, Proc. of the 4th Italian Conference Algorithms and Complexity (CIAC), pp.306-315, 2000.
DOI : 10.1007/3-540-46521-9_25

A. Tiskin, Faster subsequence recognition in compressed strings, Journal of Mathematical Sciences, vol.24, issue.6
DOI : 10.1007/s10958-009-9396-0

A. Tiskin, All Semi-local Longest Common Subsequences in Subquadratic Time, Proc. of the 1st Computer Science symposium in Russia (CSR), pp.352-363, 2006.
DOI : 10.1007/11753728_36

R. Wagner and M. Fischer, The String-to-String Correction Problem, Journal of the ACM, vol.21, issue.1, pp.168-173, 1974.
DOI : 10.1145/321796.321811

J. Ziv and A. Lempel, On the complexity of finite sequences, IEEE Transactions on Information Theory, vol.22, issue.1, pp.75-81, 1976.

J. Ziv and A. Lempel, A universal algorithm for sequential data compression, IEEE Transactions on Information Theory, vol.23, issue.3, pp.337-343, 1977.
DOI : 10.1109/TIT.1977.1055714