### Improved bounds on the average length of longest common subsequencesImproved bounds on the average length of longest common subsequences

Access Restriction
Subscribed

 Author Lueker, George S. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Arratia-Steele conjecture ♦ Longest common subsequences ♦ Average-case analysis ♦ Dynamic programming Abstract It has long been known [Chvátal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length $\textit{n}$ over an alphabet of size $\textit{k}$ is asymptotic to $γ_{k}n$ for some constant $γ_{k}$ depending on $\textit{k}.$ The value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. We discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. To our knowledge, the previous best-known lower and upper bounds for $γ_{2}$ were those of Dančík and Paterson, approximately 0.773911 and 0.837623 [Dančík 1994; Dančík and Paterson 1995]. We improve these to 0.788071 and 0.826280. This upper bound is less than the $γ_{2}$ given by Steele's old conjecture (see Steele [1997, page 3]) that $γ_{2}$ = 2/(1 + &sqrt;2)≈ 0.828427. (As Steele points out, experimental evidence had already suggested that this conjectured value was too high.) Finally, we show that the upper bound technique described here could be used to produce, for any $\textit{k},$ a sequence of upper bounds converging to $γ_{k},$ though the computation time grows very quickly as better bounds are guaranteed. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-05-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 3 Page Count 38 Starting Page 1 Ending Page 38

#### Open content in new tab

Source: ACM Digital Library