High precision simulations of the longest common subsequence problem

Details High precision simulations of the longest common subsequence problem High precision simulations of the longest common subsequence problem

2001-06-17

arxiv.org/abs/cond-mat/0106326v1

Physics

Condensed Matter

Statistical Mechanics

8 pages, 4 figures

Scientific paper

10.1007/s100510170102

The longest common subsequence problem is a long studied prototype of pattern matching problems. In spite of the effort dedicated to it, the numerical value of its central quantity, the Chvatal-Sankoff constant, is not yet known. Numerical estimations of this constant are very difficult due to finite size effects. We propose a numerical method to estimate the Chvatal-Sankoff constant which combines the advantages of an analytically known functional form of the finite size effects with an efficient multi-spin coding scheme. This method yields very high precision estimates of the Chvatal-Sankoff constant. Our results correct earlier estimates for small alphabet size while they are consistent with (albeit more precise than) earlier results for larger alphabet size.

Affiliated with

Also associated with

No associations

Rating

High precision simulations of the longest common subsequence problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with High precision simulations of the longest common subsequence problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and High precision simulations of the longest common subsequence problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-555052