Files and links (1)
Preprint (Author's original)arXiv.org - Non-exclusive license to distribute, Open
Preprint
Longest common subsequences and the Bernoulli matching model: numerical work and analyses of the r-reach simplification
ArXiv.org
18 Dec 2004
Abstract
The expected length of longest common subsequences is a problem that has been
in the literature for at least twenty five years. Determining the limiting
constants \gamma_k appears to be quite difficult, and the current best bounds
leave much room for improvement. Boutet de Monvel explores an independent
version of the problem he calls the Bernoulli Matching model. He explores this
problem and its relation to the longest common subsequence problem. This paper
continues this pursuit by focusing on a simplification we term r-reach. For the
string model, L_r(u,v) is the longest common subsequence of u and v given that
each matched pair of letters is no more than r letters apart.
Metrics
4 Record Views
Details
- Title
- Longest common subsequences and the Bernoulli matching model: numerical work and analyses of the r-reach simplification
- Creators
- Jonah Blasiak
- Publication Details
- ArXiv.org
- Resource Type
- Preprint
- Language
- English
- Academic Unit
- Mathematics
- Other Identifier
- 991021862255304721