{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,5,1]],"date-time":"2022-05-01T02:28:13Z","timestamp":1651372093384},"reference-count":19,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2009,5]]},"abstract":"\n It has long been known [Chv\u00e1tal and Sankoff 1975] that the average length of the longest common subsequence of two random strings of length\n n<\/jats:italic>\n over an alphabet of size\n k<\/jats:italic>\n is asymptotic to \u03b3\n \n k<\/jats:italic>\n <\/jats:sub>\n n<\/jats:italic>\n for some constant \u03b3\n \n k<\/jats:italic>\n <\/jats:sub>\n depending on\n k<\/jats:italic>\n . The value of these constants remains unknown, and a number of papers have proved upper and lower bounds on them. We discuss techniques, involving numerical calculations with recurrences on many variables, for determining lower and upper bounds on these constants. To our knowledge, the previous best-known lower and upper bounds for \u03b3\n 2<\/jats:sub>\n were those of Dan\u010d\u00edk and Paterson, approximately 0.773911 and 0.837623 [Dan\u010d\u00edk 1994; Dan\u010d\u00edk and Paterson 1995]. We improve these to 0.788071 and 0.826280. This upper bound is less than the \u03b3\n 2<\/jats:sub>\n given by Steele's old conjecture (see Steele [1997, page 3]) that \u03b3\n 2<\/jats:sub>\n = 2\/(1 + \u221a2)\u2248 0.828427. (As Steele points out, experimental evidence had already suggested that this conjectured value was too high.) Finally, we show that the upper bound technique described here could be used to produce, for any\n k<\/jats:italic>\n , a sequence of upper bounds converging to \u03b3\n \n k<\/jats:italic>\n <\/jats:sub>\n , though the computation time grows very quickly as better bounds are guaranteed.\n <\/jats:p>","DOI":"10.1145\/1516512.1516519","type":"journal-article","created":{"date-parts":[[2009,5,19]],"date-time":"2009-05-19T16:47:42Z","timestamp":1242751662000},"page":"1-38","source":"Crossref","is-referenced-by-count":20,"title":["Improved bounds on the average length of longest common subsequences"],"prefix":"10.1145","volume":"56","author":[{"given":"George S.","family":"Lueker","sequence":"first","affiliation":[{"name":"University of California, Irvine, California"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004903"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840365"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000125"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2307\/3212444"},{"key":"e_1_2_1_5_1","unstructured":"Dan\u010d\u00edk V. 1994. Expected length of longest common subsequences. Ph.D. dissertation Department of Computer Science University of Warwick. Dan\u010d\u00edk V. 1994. Expected length of longest common subsequences. Ph.D. dissertation Department of Computer Science University of Warwick."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060408"},{"key":"e_1_2_1_7_1","unstructured":"Gosling J. Joy B. Steele G. and Bracha G. 2005. The JavaTM Language Specification Third ed. Addison-Wesley Reading MA. Gosling J. Joy B. Steele G. and Bracha G. 2005. The Java TM Language Specification Third ed. Addison-Wesley Reading MA."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/322033.322044"},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York. Janson S. Luczak T. and Rucinski A. 2000. Random Graphs. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley New York.","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979223842X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.012"},{"key":"e_1_2_1_12_1","unstructured":"Kiwi M. and Soto J. 2008. On a speculated relation between Chv\u00e1tal-Sankoff constants of several sequences. Combinatorics Probability and Computing. To appear. Available on-line at http:\/\/arxiv.org\/abs\/0810.1066. 10.1017\/S0963548309009900 Kiwi M. and Soto J. 2008. On a speculated relation between Chv\u00e1tal-Sankoff constants of several sequences. Combinatorics Probability and Computing. To appear. Available on-line at http:\/\/arxiv.org\/abs\/0810.1066. 10.1017\/S0963548309009900"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144599359449"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Rahgavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA. Motwani R. and Rahgavan P. 1995. Randomized Algorithms. Cambridge University Press Cambridge MA.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Overton M. L. 2001. Numerical Computing with IEEE Floating Point Arithmetic. Society for Industrial and Applied Mathematics Philadelphia PA. Overton M. L. 2001. Numerical Computing with IEEE Floating Point Arithmetic. Society for Industrial and Applied Mathematics Philadelphia PA.","DOI":"10.1137\/1.9780898718072"},{"key":"e_1_2_1_16_1","volume-title":"MFCS'94","author":"Paterson M.","year":"1994"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Pevzner P. A. 2000. Computational Molecular Biology: An Algorithmic Approach. The MIT Press Cambridge MA. Pevzner P. A. 2000. Computational Molecular Biology: An Algorithmic Approach. The MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/2022.001.0001"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Seneta E. 1981. Non-negative Matrices and Markov Chains 2nd ed. Springer Series in Statistics. Springer-Verlag New York. Seneta E. 1981. Non-negative Matrices and Markov Chains 2nd ed. Springer Series in Statistics. Springer-Verlag New York.","DOI":"10.1007\/0-387-32792-4"},{"key":"e_1_2_1_19_1","volume-title":"Probability Theory and Combinatorial Optimization. CBMS-NSF Regional Conference Series in Applied Mathematics. Society for Industrial and Applied Mathematics","author":"Steele J. M.","year":"1997"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1516512.1516519","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T13:19:44Z","timestamp":1613654384000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1516512.1516519"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,5]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2009,5]]}},"alternative-id":["10.1145\/1516512.1516519"],"URL":"http:\/\/dx.doi.org\/10.1145\/1516512.1516519","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2009,5]]}}}