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.

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 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
Publisher:	SPRINGER-VERLAG BERLIN
ISBN:	3-540-60044-2
ISSN:	0302-9743
Editor:	Galil, Z and Ukkonen, E
Date:	1995
Volume:	937
Number of Pages:	9
Page Range:	pp. 55-63
Publication Status:	Published
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
URI:	http://wrap.warwick.ac.uk/id/eprint/18972

Data sourced from Thomson Reuters' Web of Knowledge

Request changes to a record

Actions (login required)

View Item