Publication at Faculty of Mathematics and Physics |
2005
Abstract
We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that the expectation of L divided by n converges to a constant.
We prove a conjecture of Sankoff and Mainville from the early 80's giving the limit of this constant for k tending to infinity.