Bounding the expected length of longest common subsequences and forests

DOI10.1007/S002240000125MaRDI QIDQ1293550zbMATH OpenOpenAlexFDO

Authors Ricardo Baeza-Yates, Ricard Gavaldà, Gonzalo Navarro, Rodrigo Scheihing

Publication date 28 June 1999

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s002240000125

zbMATH Keywords

Markov chainstwo random sequences

Mathematics Subject Classification ID

Pattern recognition, speech recognition (68T10) Searching and sorting (68P10)

Recommendations

• scientific article; zbMATH DE number 2079331
• Upper bounds for the expected length of a longest common subsequence of two binary sequences
• Improved bounds on the average length of longest common subsequences
• Large deviations-based upper bounds on the expected relative length of longest common subsequences
• LATIN 2004: Theoretical Informatics

Cited in

(18)

• Standard deviation of the longest common subsequence
• Optimal alignments of longest common subsequences and their path properties
• Letter change bias and local uniqueness in optimal sequence alignments
• On the rate of convergence for the length of the longest common subsequences in hidden Markov models
• 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
• scientific article; zbMATH DE number 5873671 (Why is no real title available?)
• 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
• The rate of the convergence of the mean score in random sequence comparison
• Approximation to the mean curve in the LCS problem
• Expected length of the longest common subsequence for large alphabets
• Thermodynamical approach to the longest common subsequence problem
• A Formula for the Mean Length of the Longest Common Subsequence
• Bounds and estimates on the average edit distance
• LATIN 2004: Theoretical Informatics

This page was built for publication: Bounding the expected length of longest common subsequences and forests

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