Bounding the Expected Length of Longest Common Subsequences and Forests
Ricardo Baeza-Yates, Ricard Gavaldá, Gonzalo Navarro and Rodrigo Scheihing
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.