A Formula for the Mean Length of the Longest Common Subsequence

DOI10.17516/1997-1397-2017-10-1-71-74MaRDI QIDQ5853068zbMATH OpenOpenAlexFDO

Authors S. V. Znamenskij

Publication date 18 March 2021

Published in Journal of Siberian Federal University. Mathematics & Physics (Search for Journal in Brave)

Full work available at URL http://mathnet.ru/eng/jsfu526

zbMATH Keywords

asymptotic formulaexpected valueLCS lengthlongest common subsequencesimulation

Mathematics Subject Classification ID

Probability theory and stochastic processes (60-XX) Statistical mechanics, structure of matter (82-XX)

Recommendations

• LATIN 2004: Theoretical Informatics
• Expected length of the longest common subsequence for large alphabets
• The rate of convergence of the mean length of the longest common subsequence
• On the order of the central moments of the length of the longest common subsequences in random words
• Common Subsequences and Supersequences and their Expected Length

Cites work

• Bounding the expected length of longest common subsequences and forests
• Expected length of the longest common subsequence for large alphabets
• Improved bounds on the average length of longest common subsequences
• Longest common subsequences of two random sequences

Cited in

(1)

• Average length of the longest \(k\)-alternating subsequence

This page was built for publication: A Formula for the Mean Length of the Longest Common Subsequence

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5853068)