Some limit results for longest common subsequences

DOI10.1016/0012-365X(79)90057-8zbMath0403.68064MaRDI QIDQ1256321

Joseph G. Deken

Publication date: 1979

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Longest Common SubsequenceSimple Matching Algorithm

Mathematics Subject Classification ID

Discrete mathematics in relation to computer science (68R99)

Related Items

Maximal success durations for a semi-Markov process, Approximation of subadditive functions and convergence rates in limiting-shape results, Upper bounds for the expected length of a longest common subsequence of two binary sequences, Longest common subsequences, 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, Approximation to the mean curve in the LCS problem, Unnamed Item, Length of the Longest Common Subsequence between Overlapping Words, The harmonic mean formula for probabilities of unions: Applications to sparse random graphs, An analytic study of the phase transition line in local sequence alignment with gaps, Stanislaw M. Ulam's contributions to theoretical biology

Cites Work

• Subadditive ergodic theory
• The tree-to-tree editing problem
• An algorithm for the distance between two finite sequences
• Longest common subsequences of two random sequences
• A Method for the Correction of Garbled Words Based on the Levenshtein Metric
• Bounds on the Complexity of the Longest Common Subsequence Problem
• Algorithms for the Longest Common Subsequence Problem
• The String-to-String Correction Problem