Bounding the Expected Length of Longest Common Subsequences and Forests

We present improvements to two techniques to find lower and upper bounds for the expected length of longest common subsequences and forests of two random sequences of the same length, over a fixed size, uniformly distributed alphabet. We emphasize the power of the methods used, which are Markov chains and Kolmogorov complexity. As a corollary, we obtain some new lower and upper bounds for the problems addressed as well as some new exact results for short sequences. 1 Introduction The longest common subsequence (LCS) of two strings is one of the main problems in combinatorial pattern matching. The LCS problem is related to DNA or protein alignments, file comparison, speech recognition, etc. We say that s is a subsequence of u if we can obtain s by deleting zero or more letters of u. The LCS of two strings u and v of length n is defined as the longest subsequence s common to u and v. For example, the LCS of longest and large is lge. An open problem related to the LCS is its expected le..