pith. sign in

arxiv: math/0308234 · v1 · submitted 2003-08-25 · 🧮 math.CO · math.PR

Expected length of the longest common subsequence for large alphabets

classification 🧮 math.CO math.PR
keywords commonexpectedgoeslengthlongestsubsequencealphabetalphabets
0
0 comments X
read the original 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 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. High-Rate Public-Key Pseudorandom Codes for Edit Errors

    cs.CR 2026-05 unverdicted novelty 6.0

    First high-rate public-key binary PRCs for edit channels via reduction from Hamming-robust PRCs and alphabet-size constructions attaining near-Singleton rates.