Bounding the expected length of longest common subsequences and forests

DOI10.1007/S002240000125zbMATH Open0934.68043OpenAlexW1988684690MaRDI QIDQ1293550FDOQ1293550

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

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

zbMATH Keywords

Markov chainstwo random sequences

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• Lower bounds for moments of global scores of pairwise Markov chains
• 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
• 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
• A Formula for the Mean Length of the Longest Common Subsequence
• Thermodynamical approach to the longest common subsequence problem
• 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)