Improved bounds on the average length of longest common subsequences

DOI10.1145/1516512.1516519zbMATH Open1325.68308OpenAlexW2091419774WikidataQ56171968 ScholiaQ56171968MaRDI QIDQ3452214FDOQ3452214

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

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

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)

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
• Length of the longest common subsequence between overlapping words
• Average length of the longest \(k\)-alternating subsequence
• Title not available (Why is that?)
• 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
• Bounds and estimates on the average edit distance
• On the asymptotic average length of a maximum common subsequence for words over a finite alphabet

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)