Bounding the expected length of longest common subsequences and forests

DOI10.1007/s002240000125zbMath0934.68043OpenAlexW1988684690MaRDI QIDQ1293550

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

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

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

Related Items (12)

Periodic words, common subsequences and frogs ⋮ Optimal alignments of longest common subsequences and their path properties ⋮ The rate of the convergence of the mean score in random sequence comparison ⋮ Letter change bias and local uniqueness in optimal sequence alignments ⋮ Thermodynamical approach to the longest common subsequence problem ⋮ Large deviations-based upper bounds on the expected relative length of longest common subsequences ⋮ On a Speculated Relation Between Chvátal–Sankoff Constants of Several Sequences ⋮ Lower bounds for moments of global scores of pairwise Markov chains ⋮ Approximation to the mean curve in the LCS problem ⋮ Standard deviation of the longest common subsequence ⋮ A Formula for the Mean Length of the Longest Common Subsequence ⋮ Expected length of the longest common subsequence for large alphabets

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