|
Zapiski Nauchnykh Seminarov POMI, 2022, Volume 517, Pages 191–224
(Mi znsl7288)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
The Chvátal–Sankoff problem: Understanding random string comparison through stochastic processes
A. Tiskinab a Department of Mathematics and Computer Science, St. Petersburg State University
b St. Petersburg Electrotechnical University “LETI”
Abstract:
Given two equally long, uniformly random binary\break strings, the expected length of their longest common subsequence (LCS) is asymptotically proportional to the strings' length. Finding the proportionality coefficient $\gamma$, i.e. the limit of the normalised LCS length for two random binary strings of length $n \to \infty$, is a very natural problem, first posed by Chvátal 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 $\gamma$ 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 $\gamma$ 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átal–Sankoff problem, albeit in a somewhat unexpected way with a rather negative flavour.
Key words and phrases:
random strings, longest common subsequence, the Chvátal–Sankoff problem, particle processes.
Received: 25.10.2022
Citation:
A. Tiskin, “The Chvátal–Sankoff problem: Understanding random string comparison through stochastic processes”, Representation theory, dynamical systems, combinatorial methods. Part XXXIV, Zap. Nauchn. Sem. POMI, 517, POMI, St. Petersburg, 2022, 191–224
Linking options:
https://www.mathnet.ru/eng/znsl7288 https://www.mathnet.ru/eng/znsl/v517/p191
|
Statistics & downloads: |
Abstract page: | 65 | Full-text PDF : | 26 | References: | 14 |
|