On a speculated relation between Chvàtal-Sankoff constants of several sequences
From MaRDI portal
Abstract: It is well known that, when normalized by n, the expected length of a longest common subsequence of d sequences of length n over an alphabet of size sigma converges to a constant gamma_{sigma,d}. We disprove a speculation by Steele regarding a possible relation between gamma_{2,d} and gamma_{2,2}. In order to do that we also obtain new lower bounds for gamma_{sigma,d}, when both sigma and d are small integers.
Recommendations
- Improved bounds on the average length of longest common subsequences
- Common Subsequences and Supersequences and their Expected Length
- Expected length of the longest common subsequence for large alphabets
- LATIN 2004: Theoretical Informatics
- The rate of convergence of the mean length of the longest common subsequence
Cites work
- A variational problem for random Young tableaux
- An Efron-Stein inequality for nonsymmetric statistics
- Bounding the expected length of longest common subsequences and forests
- Common Subsequences and Supersequences and their Expected Length
- Expected length of the longest common subsequence for large alphabets
- scientific article; zbMATH DE number 1557065 (Why is no real title available?)
- Longest common subsequences of two random sequences
- Some limit results for longest common subsequences
- The Longest Chain Among Random Points in Euclidean Space
- The rate of convergence of the mean length of the longest common subsequence
- Upper bounds for the expected length of a longest common subsequence of two binary sequences
This page was built for publication: On a speculated relation between Chvàtal-Sankoff constants of several sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3552511)
