{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T11:49:31Z","timestamp":1759146571657},"publisher-location":"Berlin, Heidelberg","reference-count":16,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540560241"},{"type":"electronic","value":"9783540473572"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1992]]},"DOI":"10.1007\/3-540-56024-6_7","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T10:53:55Z","timestamp":1330253635000},"page":"79-89","source":"Crossref","is-referenced-by-count":3,"title":["Matrix longest common subsequence problem, duality and hilbert bases"],"prefix":"10.1007","author":[{"given":"Pavel A.","family":"Pevzner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael S.","family":"Waterman","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,6,4]]},"reference":[{"key":"7_CR1","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0020-0190(86)90044-X","volume":"23","author":"A. Apostolico","year":"1986","unstructured":"Apostolico A.: Improving the worst-case perfomance of the Hunt-Szymanski strategy for the longest common subsequence of two strings. Inform. Process. Lett. 23 (1986) 63\u201369","journal-title":"Inform. Process. Lett."},{"key":"7_CR2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"Apostolico A., Guerra C.: The longest common subsequence problem revisited. Algoritmica 2 (1987) 315\u2013336","journal-title":"Algoritmica"},{"key":"7_CR3","doi-asserted-by":"crossref","unstructured":"Chow E.T., Hunkapiller T., Peterson J.C., Zimmerman B.A., Waterman M.S.: A systolic array processor for biological information signal processing. Proc. of International Conference on Supercomputing (ICS-91) June 17\u201321, 1991 (to appear)","DOI":"10.1145\/109025.109081"},{"key":"7_CR4","doi-asserted-by":"crossref","first-page":"63","DOI":"10.1016\/0095-8956(86)90064-X","volume":"40","author":"W. Cook","year":"1986","unstructured":"Cook W., Fonlupt J., Schrijver A.: An integer analogue of Caratheodory's theorem. J. of Combinatorial Theory (B) 40 (1986) 63\u201370","journal-title":"J. of Combinatorial Theory (B)"},{"key":"7_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"R.P. Dilworth","year":"1950","unstructured":"Dilworth R.P.: A decomposition theorem for partially ordered sets Ann. Math. 51 (1950) 161\u2013165","journal-title":"Ann. Math."},{"key":"7_CR6","doi-asserted-by":"crossref","first-page":"600","DOI":"10.2307\/2371374","volume":"63","author":"B. Dushnik","year":"1941","unstructured":"Dushnik B., Miller E.W.: Partially ordered sets. Am. J. Math. 63 (1941) 600\u2013610","journal-title":"Am. J. Math."},{"key":"7_CR7","unstructured":"Eppstein D., Galil Z., Giancarlo R., Italiano G. F. Sparse dynamic programming; Extended Abstract Proc. first ACM-SIAM SODA (1990) 513\u2013522"},{"key":"7_CR8","doi-asserted-by":"crossref","first-page":"168","DOI":"10.1007\/BF01584085","volume":"1","author":"D.R. Fulkerson","year":"1971","unstructured":"Fulkerson D.R.: Blocking and antiblocking polyhedra. Mathematical programming. 1 (1971) 168\u2013194","journal-title":"Mathematical programming"},{"key":"7_CR9","doi-asserted-by":"crossref","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D.S. Hirscberg","year":"1977","unstructured":"Hirscberg D.S. Algorithms for the longest common subsequence problem. J. ACM 24 (1977) 664\u2013675","journal-title":"J. ACM"},{"key":"7_CR10","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J.W. Hunt","year":"1977","unstructured":"Hunt J.W., Szymanski T.G.: A fast algorithm for computing longest common subsequences. Comm. ACM 20 (1977) 350\u2013353","journal-title":"Comm. ACM"},{"key":"7_CR11","volume-title":"Dimension theory for ordered sets","author":"D. Kelly","year":"1982","unstructured":"Kelly D., Trotter W.T.: Dimension theory for ordered sets. In I. Rival (ed.) Ordered sets Reidel, Dordrecht\/Boston (1982)"},{"key":"7_CR12","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1016\/0022-2836(70)90057-4","volume":"48","author":"S.B. Needleman","year":"1970","unstructured":"Needleman S.B., Wunsch C.D.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol. 48 (1970) 443\u2013453","journal-title":"J. Mol. Biol."},{"key":"7_CR13","unstructured":"Pevzner P., Waterman M.: Generalized sequence alignment and duality. Adv. in Appl. Math. (1992) (in press)"},{"key":"7_CR14","unstructured":"Sagan B.E.: The symmetric group. Representations, combinatorial algorithms and symmetric functions. Wadsworth and Brooks\/Cole (1991)"},{"key":"7_CR15","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1073\/pnas.69.1.4","volume":"69","author":"D. Sankoff","year":"1972","unstructured":"Sankoff D.: Matching sequences under deletion-insertion constraints. Proc. Nat. Acad. Sci. USA 69 (1972) 4\u20136","journal-title":"Proc. Nat. Acad. Sci. USA"},{"key":"7_CR16","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/0024-3795(81)90005-7","volume":"38","author":"A. Schrijver","year":"1981","unstructured":"Schrijver A.: On total dual integrality. Linear algebra and its applications. 38 (1981) 27\u201332","journal-title":"Linear algebra and its applications"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Pattern Matching"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-56024-6_7.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T00:48:25Z","timestamp":1619570905000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-56024-6_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1992]]},"ISBN":["9783540560241","9783540473572"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/3-540-56024-6_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1992]]}}}