Common subsequences and supersequences and their expected length
UNSPECIFIED (1995) Common subsequences and supersequences and their expected length. In: 6th Annual Symposium on Combinatorial Pattern Matching (CPM 95), ESPOO, FINLAND, JUL 05-07, 1995. Published in: COMBINATORIAL PATTERN MATCHING, 937 pp. 55-63.Full text not available from this repository.
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 Ic. It is known that there are constants gamma(k)((l)) such that f(n, k, l) --> gamma(k)((l)) n, we show that gamma(k)((l)) = Theta(k(1/l-1)). Bounds for the corresponding constants for the expected length of a shortest common supersequence are also presented.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||COMBINATORIAL PATTERN MATCHING|
|Editor:||Galil, Z and Ukkonen, E|
|Number of Pages:||9|
|Page Range:||pp. 55-63|
|Title of Event:||6th Annual Symposium on Combinatorial Pattern Matching (CPM 95)|
|Location of Event:||ESPOO, FINLAND|
|Date(s) of Event:||JUL 05-07, 1995|
Actions (login required)