Common subsequences and supersequences and their expected length
UNSPECIFIED. (1998) Common subsequences and supersequences and their expected length. COMBINATORICS PROBABILITY & COMPUTING, 7 (4). pp. 365-373. ISSN 0963-5483Full text not available from this repository.
Let f(n,k, l) be the expected length of a longest common subsequence of I sequences of length n over an alphabet of size k. It is known that there are constants y(k)((l))) such that f(n,k, l) --> gamma(k)((l))n as n --> infinity , and we show that gamma(k)((l)) = Theta(k(1/1-1)) as k --> infinity . Bounds for the k k corresponding constants for the expected length of a shortest common supersequence are also presented.
|Item Type:||Journal Article|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QA Mathematics
|Journal or Publication Title:||COMBINATORICS PROBABILITY & COMPUTING|
|Publisher:||CAMBRIDGE UNIV PRESS|
|Official Date:||December 1998|
|Number of Pages:||9|
|Page Range:||pp. 365-373|
Actions (login required)