{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T19:38:06Z","timestamp":1784403486987,"version":"3.55.0"},"reference-count":19,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2009,7,1]],"date-time":"2009-07-01T00:00:00Z","timestamp":1246406400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2009,7]]},"abstract":"<jats:p>It is well known that, when normalized by<jats:italic>n<\/jats:italic>, the expected length of a longest common subsequence of<jats:italic>d<\/jats:italic>sequences of length<jats:italic>n<\/jats:italic>over an alphabet of size \u03c3 converges to a constant \u03b3<jats:sub>\u03c3,<jats:italic>d<\/jats:italic><\/jats:sub>. We disprove a speculation by Steele regarding a possible relation between \u03b3<jats:sub>2,<jats:italic>d<\/jats:italic><\/jats:sub>and \u03b3<jats:sub>2,2<\/jats:sub>. In order to do that we also obtain some new lower bounds for \u03b3<jats:sub>\u03c3,<jats:italic>d<\/jats:italic><\/jats:sub>, when both \u03c3 and<jats:italic>d<\/jats:italic>are small integers.<\/jats:p>","DOI":"10.1017\/s0963548309009900","type":"journal-article","created":{"date-parts":[[2009,4,28]],"date-time":"2009-04-28T09:15:41Z","timestamp":1240910141000},"page":"517-532","source":"Crossref","is-referenced-by-count":4,"title":["On a Speculated Relation Between Chv\u00e1tal\u2013Sankoff Constants of Several Sequences"],"prefix":"10.1017","volume":"18","author":[{"given":"M.","family":"KIWI","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"SOTO","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"56","published-online":{"date-parts":[[2009,7,1]]},"reference":[{"key":"S0963548309009900_ref19","doi-asserted-by":"crossref","unstructured":"[19] Waterman M. (1995) Introduction to Computational Biology: Average Case Analysis of Algorithms and Sequences. Series in Discrete Mathematics and Optimization, Chapman & Hall\/CRC.","DOI":"10.1007\/978-1-4899-6846-3"},{"key":"S0963548309009900_ref4","doi-asserted-by":"publisher","DOI":"10.1017\/S0021900200047999"},{"key":"S0963548309009900_ref5","unstructured":"[5] Dan\u010d\u00edk V. (1994) Expected length of longest common subsequences. PhD thesis, Department of Computer Science, University of Warwick."},{"key":"S0963548309009900_ref9","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"S0963548309009900_ref17","doi-asserted-by":"crossref","unstructured":"[17] Szpankowski W. (2000) Average Case Analysis of Algorithms and Sequences, Series in Discrete Mathematics and Optimization, Wiley InterScience.","DOI":"10.1002\/9781118032770"},{"key":"S0963548309009900_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s002240000125"},{"key":"S0963548309009900_ref7","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240060408"},{"key":"S0963548309009900_ref12","unstructured":"[12] Lueker G. (2003) Improved bounds on the average length of longest common subsequences. In Proc. 14th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 130\u2013131."},{"key":"S0963548309009900_ref6","doi-asserted-by":"publisher","DOI":"10.1017\/S096354839800368X"},{"key":"S0963548309009900_ref3","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1988-0943043-6"},{"key":"S0963548309009900_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(79)90057-8"},{"key":"S0963548309009900_ref13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach","author":"Pevzner","year":"2000"},{"key":"S0963548309009900_ref11","doi-asserted-by":"publisher","DOI":"10.1016\/0001-8708(77)90030-5"},{"key":"S0963548309009900_ref18","first-page":"1024","article-title":"Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux","volume":"233","author":"Vershik","year":"1977","journal-title":"Doklady Akademii Nauk SSSR"},{"key":"S0963548309009900_ref16","unstructured":"[16] Steele J. M. (1996) Probability Theory and Combinatorial Optimization, CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM."},{"key":"S0963548309009900_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2004.10.012"},{"key":"S0963548309009900_ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1177004903"},{"key":"S0963548309009900_ref15","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349952"},{"key":"S0963548309009900_ref14","unstructured":"[14] Soto J. (2006) Variantes aleatorias de la subsecuencia com\u00fan m\u00e1s grande. Departamento de Ingenier\u00eda Matem\u00e1tica, U. Chile. (In Spanish.)"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548309009900","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T18:43:02Z","timestamp":1558291382000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548309009900\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,7]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,7]]}},"alternative-id":["S0963548309009900"],"URL":"https:\/\/doi.org\/10.1017\/s0963548309009900","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,7]]}}}