Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-09T18:31:09.100Z Has data issue: false hasContentIssue false
  • English
  • Français

On a Speculated Relation Between Chvátal–Sankoff Constants of Several Sequences

Published online by Cambridge University Press:  01 July 2009

M. KIWI  and
J. SOTO
M. KIWI
Affiliation:
Departamento de Ingeniería Matemática, Centro de Modelamiento Matemático (UMI 2807, CNRS), University of Chile (e-mail: mkiwi@dim.uchile.cl)
J. SOTO
Affiliation:
Department of Mathematics, MIT, Cambridge, MA 02139, USA (e-mail: jsoto@math.mit.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

It is well known that, when normalized by n, the expected length of a longest common subsequence of d sequences of length n over an alphabet of size σ converges to a constant γσ,d. We disprove a speculation by Steele regarding a possible relation between γ2,d and γ2,2. In order to do that we also obtain some new lower bounds for γσ,d, when both σ and d are small integers.

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 18 , Issue 4 , July 2009 , pp. 517 - 532
Copyright
Copyright © Cambridge University Press 2009

References

[1]Alexander, K. S. (1994) The rate of convergence of the mean of the longest common subsequence. Ann. Appl. Probab. 4 1074–1083.CrossRefGoogle Scholar
[2]Baeza-Yates, R., Navarro, G., Gavaldá, R. and Schehing, R. (1999) Bounding the expected length of the longest common subsequences and forests. Theory Comput. Syst. 32 435–452.CrossRefGoogle Scholar
[3]Bollobás, B. and Winkler, P. (1988) The longest chain among random points in Euclidean space. Proc. Amer. Math. Soc. 103 347–353.CrossRefGoogle Scholar
[4]Chvátal, V. and Sankoff, D. (1975) Longest common subsequences of two random sequences. J. Appl. Probab. 12 306–315.CrossRefGoogle Scholar
[5]Dančík, V. (1994) Expected length of longest common subsequences. PhD thesis, Department of Computer Science, University of Warwick.Google Scholar
[6]Dančík, V. (1998) Common subsequences and supersequences and their expected length. Combin. Probab. Comput. 7 365–373.CrossRefGoogle Scholar
[7]Dančík, V. and Paterson, M. (1995) Upper bounds for the expected length of a longest common subsequence of two binary sequences. Random Struct. Alg. 6 449–458.CrossRefGoogle Scholar
[8]Deken, J. P. (1979) Some limit results for longest common subsequences. Discrete Math. 26 17–31.CrossRefGoogle Scholar
[9]Janson, S., Łuczak, T. and Rucinski, A. (2000) Random Graphs, Wiley.CrossRefGoogle Scholar
[10]Kiwi, M., Loebl, M. and Matoušek, J. (2005) Expected length of the longest common subsequence for large alphabets. Adv. Math. 197 480–498.CrossRefGoogle Scholar
[11]Logan, B. and Shepp, L. (1977) A variational problem of random Young tableaux. Adv. Math. 26 206–222.CrossRefGoogle Scholar
[12]Lueker, G. (2003) Improved bounds on the average length of longest common subsequences. In Proc. 14th Annual ACM–SIAM Symposium on Discrete Algorithms, pp. 130–131.Google Scholar
[13]Pevzner, P. (2000) Computational Molecular Biology: An Algorithmic Approach, MIT Press.CrossRefGoogle Scholar
[14]Soto, J. (2006) Variantes aleatorias de la subsecuencia común más grande. Departamento de Ingeniería Matemática, U. Chile. (In Spanish.)Google Scholar
[15]Steele, J. M. (1986) An Efron–Stein inequality for nonsymmetric statistics. Ann. Statist. 14 753–758.CrossRefGoogle Scholar
[16]Steele, J. M. (1996) Probability Theory and Combinatorial Optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM.Google Scholar
[17]Szpankowski, W. (2000) Average Case Analysis of Algorithms and Sequences, Series in Discrete Mathematics and Optimization, Wiley InterScience.Google Scholar
[18]Vershik, A. and Kerov, S. (1977) Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux. Doklady Akademii Nauk SSSR 233 1024–1028.Google Scholar
[19]Waterman, M. (1995) Introduction to Computational Biology: Average Case Analysis of Algorithms and Sequences. Series in Discrete Mathematics and Optimization, Chapman & Hall/CRC.Google Scholar