Improved bounds on the average length of longest common subsequences

DOI10.1145/1516512.1516519MaRDI QIDQ3452214zbMATH OpenOpenAlexWikidataFDO

Authors George S. Lueker

Publication date 11 November 2015

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1516512.1516519

zbMATH Keywords

dynamic programmingaverage-case analysislongest common subsequencesArratia-Steele conjecture

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Analysis of algorithms (68W40) Exact enumeration problems, generating functions (05A15) Combinatorial probability (60C05) Combinatorics on words (68R15) Algorithms on strings (68W32)

Recommendations

• scientific article; zbMATH DE number 2079331
• On the convergence of upperbBound techniques for the average length of longest common subsequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• The rate of convergence of the mean length of the longest common subsequence
• Expected length of the longest common subsequence for large alphabets

Cited in

(16)

• Quasi-random words and limits of word sequences
• On the convergence of upperbBound techniques for the average length of longest common subsequences
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Lower bounds for moments of global scores of pairwise Markov chains
• Average length of the longest \(k\)-alternating subsequence
• Length of the longest common subsequence between overlapping words
• scientific article; zbMATH DE number 2079331 (Why is no real title available?)
• On a speculated relation between Chvàtal-Sankoff constants of several sequences
• Periodic words, common subsequences and frogs
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• An iterative approach to determining the length of the longest common subsequence of two strings
• Sparse long blocks and the micro-structure of the longuest common subsequences
• The rate of convergence of the mean length of the longest common subsequence
• A Formula for the Mean Length of the Longest Common Subsequence
• On the asymptotic average length of a maximum common subsequence for words over a finite alphabet
• Bounds and estimates on the average edit distance

This page was built for publication: Improved bounds on the average length of longest common subsequences

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