Article contents
Common Subsequences and Supersequences and their Expected Length
Published online by Cambridge University Press: 01 December 1998
Abstract
Let f(n, k, l) be the expected length of a longest common subsequence of l sequences of length n over an alphabet of size k. It is known that there are constants γ(l)k such that f(n, k, l)→ γ(l)kn as n→∞, and we show that γ(l)k= Θ(k1/l−1) as k→∞. Bounds for the corresponding constants for the expected length of a shortest common supersequence are also presented.
- Type
- Research Article
- Information
- Copyright
- 1998 Cambridge University Press
- 5
- Cited by