论文标题
Chvátal-Sankoff问题：通过随机过程了解随机字符串比较
The Chvátal-Sankoff problem: Understanding random string comparison through stochastic processes
论文作者
论文摘要
给定两个同样长的，均匀的随机二进制字符串，其最长共同子序列（LC）的预期长度与弦的长度成正比成正比。找到比例系数$γ$，即两个随机长度$ n \ to \ infty $的归一化LCS长度的极限，这是一个非常自然的问题，首先是Chvátal和Sankoff于1975年提出的，尚未解决。这个问题与从组合和算法分析到编码理论和计算生物学的各种领域相关。使用统计力学方法以及LCS组合结构的一些现有结果，我们将常数$γ$与某个随机粒子过程的参数联系起来，我们用来获得$γ$的新估计。
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 $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 $γ$ to the parameters of a certain stochastic particle process, which we use to obtain a new estimate for $γ$.
