{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T22:08:19Z","timestamp":1725574099971},"publisher-location":"Berlin, Heidelberg","reference-count":24,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540212584"},{"type":"electronic","value":"9783540246985"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-24698-5_34","type":"book-chapter","created":{"date-parts":[[2011,1,7]],"date-time":"2011-01-07T22:28:22Z","timestamp":1294439302000},"page":"302-311","source":"Crossref","is-referenced-by-count":7,"title":["Expected Length of the Longest Common Subsequence for Large Alphabets"],"prefix":"10.1007","author":[{"given":"Marcos","family":"Kiwi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Loebl","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ji\u0159\u00ed","family":"Matou\u0161ek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"34_CR1","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1090\/S0273-0979-99-00796-X","volume":"36","author":"D. Aldous","year":"1999","unstructured":"Aldous, D., Diaconis, P.: Longest increasing subsequences: From patience sorting to the Baik\u2013Deift\u2013Johansson theorem. Bull. of the AMS\u00a036(4), 413\u2013432 (1999)","journal-title":"Bull. of the AMS"},{"key":"34_CR2","doi-asserted-by":"crossref","unstructured":"Baer, R., Brock, P.: Natural soritng over permutation spaces. Mathematics of Computation, 385\u2013410 (1967)","DOI":"10.2307\/2004668"},{"issue":"4","key":"34_CR3","doi-asserted-by":"publisher","first-page":"435","DOI":"10.1007\/s002240000125","volume":"32","author":"R. Baeza-Yates","year":"1999","unstructured":"Baeza-Yates, R., Navarro, G., Gavald\u00e1, R., Schehing, R.: Bounding the expected length of the longest common subsequences and forests. Theory of Computing Systems\u00a032(4), 435\u2013452 (1999)","journal-title":"Theory of Computing Systems"},{"key":"34_CR4","doi-asserted-by":"publisher","first-page":"1119","DOI":"10.1090\/S0894-0347-99-00307-0","volume":"12","author":"J. Baik","year":"1999","unstructured":"Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutaions. J. Amer. Math. Soc.\u00a012, 1119\u20131178 (1999)","journal-title":"J. Amer. Math. Soc."},{"key":"34_CR5","series-title":"Graduate Text in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0619-4","volume-title":"Modern Graph Theory","author":"B. Bollob\u00e1s","year":"1998","unstructured":"Bollob\u00e1s, B.: Modern Graph Theory. Graduate Text in Mathematics, vol.\u00a0184. Springer, Heidelberg (1998)"},{"key":"34_CR6","doi-asserted-by":"publisher","first-page":"306","DOI":"10.2307\/3212444","volume":"12","author":"V. Chv\u00e1tal","year":"1975","unstructured":"Chv\u00e1tal, V., Sankoff, D.: Longest common subsequences of two random sequences. J. Appl. Prob.\u00a012, 306\u2013315 (1975)","journal-title":"J. Appl. Prob."},{"key":"34_CR7","unstructured":"Dan\u010d\u00edk, V.: Expected Length of Longest Common Subsequences. PhD thesis, Department of Computer Science, University ofWarwick (September 1994)"},{"key":"34_CR8","first-page":"463","volume":"2","author":"P. Erd\u00f6s","year":"1935","unstructured":"Erd\u00f6s, P., Szekeres, G.: A combinatorial problem in geometry. Compositio Math.\u00a02, 463\u2013470 (1935)","journal-title":"Compositio Math."},{"issue":"2","key":"34_CR9","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1214\/aoap\/1177005939","volume":"1","author":"A. Frieze","year":"1991","unstructured":"Frieze, A.: On the length of the longest monotone subsequence in a random permutation. The Annals of Applied Prob.\u00a01(2), 301\u2013305 (1991)","journal-title":"The Annals of Applied Prob."},{"key":"34_CR10","doi-asserted-by":"publisher","first-page":"1085","DOI":"10.1023\/A:1004879725949","volume":"102","author":"J. Gravner","year":"2001","unstructured":"Gravner, J., Tracy, C., Widom, H.: Limit theorems for height fluctuations in a class of discrete space time growth models. J. Stat. Phys.\u00a0102, 1085\u20131132 (2001)","journal-title":"J. Stat. Phys."},{"key":"34_CR11","doi-asserted-by":"crossref","unstructured":"Hammersley, J.M.: A few seedlings of research. In: Proc. Sixth Berkeley Sympos. Math. Stat. Prob., Berkeley, Calif, pp. 345\u2013394. Univ. of California Press (1972)","DOI":"10.1525\/9780520325883-020"},{"key":"34_CR12","doi-asserted-by":"crossref","DOI":"10.1002\/9781118032718","volume-title":"Random Graphs","author":"S. Janson","year":"2000","unstructured":"Janson, S., Luczak, T., Rucinski, A.: Random Graphs. Wiley, Chichester (2000)"},{"key":"34_CR13","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1007\/s002200050027","volume":"209","author":"K. Johannson","year":"2000","unstructured":"Johannson, K.: Shape fluctuations and random matrices. Commun. Math. Phys.\u00a0209, 437\u2013476 (2000)","journal-title":"Commun. Math. Phys."},{"issue":"6","key":"34_CR14","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1214\/aop\/1176996798","volume":"1","author":"J.F.C. Kingman","year":"1973","unstructured":"Kingman, J.F.C.: Subadditive ergodic theory. The Annals of Prob.\u00a01(6), 883\u2013909 (1973)","journal-title":"The Annals of Prob."},{"issue":"2","key":"34_CR15","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1002\/rsa.10048","volume":"21","author":"M. Kiwi","year":"2002","unstructured":"Kiwi, M., Loebl, M.: Largest planar matching in random bipartite graphs. Random Structures and Algorithms\u00a021(2), 162\u2013181 (2002)","journal-title":"Random Structures and Algorithms"},{"key":"34_CR16","doi-asserted-by":"crossref","unstructured":"Kiwi, M., Loebl, M., Matou\u0161ek, J.: Expected length of the longest common subsequence for large alphabets. Technical Report math.CO\/0308234, ArXiv.org (August 2003)","DOI":"10.1007\/978-3-540-24698-5_34"},{"key":"34_CR17","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/0001-8708(77)90030-5","volume":"26","author":"B. Logan","year":"1977","unstructured":"Logan, B., Shepp, L.: A variational problem or random Young tableaux. Adv. in Math.\u00a026, 206\u2013222 (1977)","journal-title":"Adv. in Math."},{"key":"34_CR18","doi-asserted-by":"crossref","unstructured":"Okounkov, A.: Random matrices and ramdom permutations. International Mathematics Research Notices, 1043\u20131095 (2000)","DOI":"10.1155\/S1073792800000532"},{"key":"34_CR19","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach","author":"P. Pevzner","year":"2000","unstructured":"Pevzner, P.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000)"},{"key":"34_CR20","first-page":"363","volume-title":"Common subsequences and monotone subsequences, ch.\u00a017","year":"1983","unstructured":"Sankoff, D., Kruskal, J. (eds.): Common subsequences and monotone subsequences, ch.\u00a017, pp. 363\u2013365. Addison\u2013Wesley, Reading (1983)"},{"key":"34_CR21","doi-asserted-by":"publisher","first-page":"179","DOI":"10.4153\/CJM-1961-015-3","volume":"13","author":"C. Schensted","year":"1961","unstructured":"Schensted, C.: Longest increasing and decreasing subsequences. Canad. J. Math.\u00a013, 179\u2013191 (1961)","journal-title":"Canad. J. Math."},{"issue":"1","key":"34_CR22","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1090\/S0273-0979-02-00966-7","volume":"40","author":"R. Stanley","year":"2002","unstructured":"Stanley, R.: Recent progress in algebraic combinatorics. Bull. of the AMS\u00a040(1), 55\u201368 (2002)","journal-title":"Bull. of the AMS"},{"key":"34_CR23","first-page":"261","volume-title":"Modern Mathematics for the Engineers","author":"S. Ulam","year":"1961","unstructured":"Ulam, S.: Monte Carlo calculations in problems of mathematical physics. In: Modern Mathematics for the Engineers, pp. 261\u2013281. McGraw-Hill, New York (1961)"},{"key":"34_CR24","first-page":"1024","volume":"233","author":"A. Vershik","year":"1977","unstructured":"Vershik, A., Kerov, S.: Asymptotics of the Plancherel measure of the symmetric group and the limiting form of Young tableaux. Dokl. Akad. Nauk SSSR\u00a0233, 1024\u20131028 (1977)","journal-title":"Dokl. Akad. Nauk SSSR"}],"container-title":["Lecture Notes in Computer Science","LATIN 2004: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24698-5_34","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,17]],"date-time":"2021-11-17T02:56:08Z","timestamp":1637117768000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24698-5_34"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540212584","9783540246985"],"references-count":24,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24698-5_34","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2004]]}}}