Longest common subsequences in binary sequences

2013/07/10 by Dixon, John D.
#60C05 06A07 68W40 #Combinatorics (math.CO) #FOS: Mathematics #Group Theory (math.GR) #Probability (math.PR)

paper · doi:10.48550/arxiv.1307.2796

Abstract

Given two 0,1-sequences X and Y of lengths m and n, respectively, we write L(X,Y) to denote the length of the longest common subsequence (LCS) of X and Y, and write L(m,n) to denote the expected value of L(X,Y) when X and Y are random sequences. We study the value of the function z -> lim L(nz,n)/n (as n -> infinity) and the relation of this function to the outstanding problem of computing the Chvatal-Sankoff constant lim L(n,n)/n.

Related

• Expected Length of the Longest Common Subsequence of Multiple Strings
• Systematic assessment of the expected length, variance and distribution of Longest Common Subsequences
• Repetition-free longest common subsequence of random sequences
• Simulations, Computations, and Statistics for Longest Common Subsequences
• Improved Lower Bounds on the Expected Length of Longest Common Subsequences