Thermodynamical approach to the longest common subsequence problem
From MaRDI portal
Publication:937112
DOI10.1007/s10955-008-9533-zzbMath1214.82066MaRDI QIDQ937112
Saba Amsalu, Marina Vachkovskaia, Heinrich III Matzinger
Publication date: 20 August 2008
Published in: Journal of Statistical Physics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10955-008-9533-z
68R15: Combinatorics on words
82C22: Interacting particle systems in time-dependent statistical mechanics
60K35: Interacting random processes; statistical mechanics type models; percolation theory
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- General methods of sequence comparison
- On the longest common increasing binary subsequence
- An Efron-Stein inequality for nonsymmetric statistics
- Some limit results for longest common subsequences
- Large deviations for increasing sequences on the plane
- Bounding the expected length of longest common subsequences and forests
- Exact limiting shape for a simplified model of first-passage percolation on the plane
- A phase transition for the score in matching random sequences allowing deletions
- The rate of convergence of the mean length of the longest common subsequence
- Hammersley's interacting particle process and longest increasing subsequences
- Standard deviation of the longest common subsequence
- Approximation to the mean curve in the LCS problem
- Expected length of the longest common subsequence for large alphabets
- Longest common subsequences of two random sequences
- Upper bounds for the expected length of a longest common subsequence of two binary sequences
- Large deviations-based upper bounds on the expected relative length of longest common subsequences
- Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
- On the connection between oriented percolation and contact process
