Expected length of the longest common subsequence for large alphabets

Author	dc.contributor.author	Kiwi Krauskopf, Marcos
Author	dc.contributor.author	Loebl, Martin	es_CL
Author	dc.contributor.author	Matoušek, Jiří	es_CL
Admission date	dc.date.accessioned	2007-05-23T14:30:02Z
Available date	dc.date.available	2007-05-23T14:30:02Z
Publication date	dc.date.issued	2005-11-10
Cita de ítem	dc.identifier.citation	ADVANCES IN MATHEMATICS 197 (2): 480-498 NOV 10 2005	en
Identifier	dc.identifier.issn	0001-8708
Identifier	dc.identifier.uri	https://repositorio.uchile.cl/handle/2250/124632
Abstract	dc.description.abstract	We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield that E[L]/n converges to a constant gamma(k). We prove a conjecture of Sankoff and Mainville from the early 1980s claiming that gamma(k)root k -> 2 as k -> infinity.	en
Lenguage	dc.language.iso	en	en
Publisher	dc.publisher	ACADEMIC PRESS INC ELSEVIER SCIENCE	en
Keywords	dc.subject	RANDOM PERMUTATIONS	en
Título	dc.title	Expected length of the longest common subsequence for large alphabets	en
Document type	dc.type	Artículo de revista