Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T15:01:56.732Z Has data issue: false hasContentIssue false
  • English
  • Français

Common Subsequences and Supersequences and their Expected Length

Published online by Cambridge University Press:  01 December 1998

VLADO DANČÍK
VLADO DANČÍK
Affiliation:
Current address: Millennium Pharmaceuticals, 40 Erie Street, Cambridge, MA 02139–4254, USA (e-mail: dancik@mpi.com)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 7 , Issue 4 , December 1998 , pp. 365 - 373
Copyright
1998 Cambridge University Press