Abstract.
Let $f(n)$ be the expected length of a longest common subsequence of two random sequences over a fixed alphabet of size $k$. It is known that $f(n)\to c_kn$ for some constant $c_k$. We define a collation as a pair of sequences with marked matches. A dominated collation is a collation that is not matched optimally. Upper bounds for $c_k$ can be derived from upper bounds for the number of nondominated collations. Using local properties of matches we can eliminate many nondominated collations and improve upper bounds for $c_k$.
Full paper (79K) is available in compressed postscript format.
Bibtex entries:
@Article{Dan94, author = "Vlado Dan{\v c}{\'\i}k", title = "Upper bounds for the expected length of a longest common subsequence", journal = "Bulletin of EATCS", year = "1994", volume = "54", pages = "248", month = "October", note = "Abstract" }