Expected length of the longest common subsequence for large alphabets

Details Expected length of the longest common subsequence for large alphabets Expected length of the longest common subsequence for large alphabets

2003-08-25

arxiv.org/abs/math/0308234v1

Mathematics

Combinatorics

14 pages, 1 figure, LaTex

Scientific paper

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 expected value of L, when normalized by
n, converges to a constant C_k. We prove a conjecture of Sankoff and Mainville
from the early 80's claiming that C_k\sqrt{k} goes to 2 as k goes to infinity.

Affiliated with

Also associated with

No associations

Rating

Expected length of the longest common subsequence for large alphabets does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Expected length of the longest common subsequence for large alphabets, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Expected length of the longest common subsequence for large alphabets will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-629494