The Library
Common subsequences and supersequences and their expected length
Tools
UNSPECIFIED (1998) Common subsequences and supersequences and their expected length. COMBINATORICS PROBABILITY & COMPUTING, 7 (4). pp. 365-373. ISSN 0963-5483.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
Abstract
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 | ||||
ISSN: | 0963-5483 | ||||
Official Date: | December 1998 | ||||
Dates: |
|
||||
Volume: | 7 | ||||
Number: | 4 | ||||
Number of Pages: | 9 | ||||
Page Range: | pp. 365-373 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |