Expected length of the longest common subsequence for large alphabets
| dc.creator | Kiwi, Marcos | |
| dc.creator | Loebl, Martin | |
| dc.creator | Matousek, Jiri | |
| dc.date | 2003-08-25 | |
| dc.date.accessioned | 2026-07-07T05:00:36Z | |
| dc.date.available | 2026-07-07T05:00:36Z | |
| dc.description | 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 the expected value of L, when normalized by n, converges to a constant C_k. We prove a conjecture of Sankoff and Mainville from the early 80's claiming that C_k\sqrt{k} goes to 2 as k goes to infinity. | |
| dc.description | 14 pages, 1 figure, LaTex | |
| dc.identifier | https://arxiv.org/abs/math/0308234 | |
| dc.identifier | http://arxiv.org/abs/math/0308234 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/68379 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | Expected length of the longest common subsequence for large alphabets | |
| dc.type | text |