The Chv\'atal-Sankoff problem: Understanding random string comparison through stochastic processes
From MaRDI portal
Abstract: Given two equally long, uniformly random binary strings, the expected length of their longest common subsequence (LCS) is asymptotically proportional to the strings' length. Finding the proportionality coefficient , i.e. the limit of the normalised LCS length for two random binary strings of length , is a very natural problem, first posed by Chv'atal and Sankoff in 1975, and as yet unresolved. This problem has relevance to diverse fields ranging from combinatorics and algorithm analysis to coding theory and computational biology. Using methods of statistical mechanics, as well as some existing results on the combinatorial structure of LCS, we link constant to the parameters of a certain stochastic particle process. These parameters are determined by a specific (large) system of polynomial equations with integer coefficients, which implies that is an algebraic number. Short of finding an exact closed-form solution for such a polynomial system, which appears to be unlikely, our approach essentially resolves the Chv'atal-Sankoff problem, albeit in a somewhat unexpected way with a rather negative flavour.
This page was built for publication: The Chv\'atal-Sankoff problem: Understanding random string comparison through stochastic processes
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419414)
