Large deviation based upper bounds for the LCS-problem

We analyse and apply a large deviation and Montecarlo simulation based method for the computation of improved upper bounds on the Chvatal-Sankoff constant for i.i.d. random sequences over a finite alphabet. Our theoretical results show that this method converges to the exact value of when a control...

Celý popis

Podrobná bibliografie
Hlavní autoři: Hauser, R, Martinez, S, Matzinger, H
Médium: Report
Vydáno: Unspecified 2003
Popis
Shrnutí:We analyse and apply a large deviation and Montecarlo simulation based method for the computation of improved upper bounds on the Chvatal-Sankoff constant for i.i.d. random sequences over a finite alphabet. Our theoretical results show that this method converges to the exact value of when a control parameter converges to infinity. We also give upper bounds on the complexity for numerically computing the Chvatal-Sankoff constant to any given precision via this method. Our numerical experiments confirm the theory and allow us to give new upper bounds that are correct to two digits.