{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T18:36:06Z","timestamp":1725561366070},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540206958"},{"type":"electronic","value":"9783540245872"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/978-3-540-24587-2_11","type":"book-chapter","created":{"date-parts":[[2010,7,29]],"date-time":"2010-07-29T08:59:19Z","timestamp":1280393959000},"page":"88-97","source":"Crossref","is-referenced-by-count":1,"title":["The Intractability of Computing the Hamming Distance"],"prefix":"10.1007","author":[{"given":"Bodo","family":"Manthey","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R\u00fcdiger","family":"Reischuk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"issue":"4","key":"11_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"A.V. Aho","year":"1972","unstructured":"Aho, A.V., Petersen, T.G.: A minimum distance error-correcting parser for context-free languages. SIAM Journal on Computing\u00a01(4), 305\u2013312 (1972)","journal-title":"SIAM Journal on Computing"},{"key":"11_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"R.G. Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Heidelberg (1999)"},{"issue":"1","key":"11_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/BF01744431","volume":"17","author":"M. Furst","year":"1984","unstructured":"Furst, M., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory\u00a017(1), 13\u201327 (1984)","journal-title":"Mathematical Systems Theory"},{"key":"11_CR4","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195085914.001.0001","volume-title":"Limits to Parallel Computation: P-Completeness Theory","author":"R. Greenlaw","year":"1995","unstructured":"Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to Parallel Computation: P-Completeness Theory. Oxford University Press, Oxford (1995)"},{"key":"11_CR5","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D.M. Gusfield","year":"1997","unstructured":"Gusfield, D.M.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"issue":"4","key":"11_CR6","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0020-0190(93)90022-2","volume":"46","author":"M.M. Halld\u00f3rsson","year":"1993","unstructured":"Halld\u00f3rsson, M.M.: Approximating the minimum maximal independence number. Information Processing Letters\u00a046(4), 169\u2013172 (1993)","journal-title":"Information Processing Letters"},{"key":"11_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/3-540-52921-7_71","volume-title":"Algorithms","author":"L.A. Hemachandra","year":"1990","unstructured":"Hemachandra, L.A.: Algorithms from complexity theory: Polynomial-time operations for complex sets. In: Asano, T., Imai, H., Ibaraki, T., Nishizeki, T. (eds.) SIGAL 1990. LNCS, vol.\u00a0450, pp. 221\u2013231. Springer, Heidelberg (1990)"},{"issue":"11","key":"11_CR8","doi-asserted-by":"publisher","first-page":"669","DOI":"10.1145\/368310.368385","volume":"6","author":"E.T. Irons","year":"1963","unstructured":"Irons, E.T.: An error-correcting parse algorithm. Communications of the ACM\u00a06(11), 669\u2013673 (1963)","journal-title":"Communications of the ACM"},{"key":"11_CR9","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Mapping the genome: Some combinatorial problems arising in molecular biology. In: Proc. of the 25th Ann. ACM Symp. on Theory of Computing (STOC), pp. 278\u2013285 (1993)","DOI":"10.1145\/167088.167170"},{"issue":"1","key":"11_CR10","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R.E. Ladner","year":"1975","unstructured":"Ladner, R.E.: The circuit value problem is log space complete for P. SIGACT News\u00a07(1), 18\u201320 (1975)","journal-title":"SIGACT News"},{"issue":"1","key":"11_CR11","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/360767.360771","volume":"17","author":"G. Lyon","year":"1974","unstructured":"Lyon, G.: Syntax-directed least-errors analysis for context-free languages: A practical approach. Communications of the ACM\u00a017(1), 3\u201314 (1974)","journal-title":"Communications of the ACM"},{"issue":"1","key":"11_CR12","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Computing Surveys\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Computing Surveys"},{"key":"11_CR13","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/2022.001.0001","volume-title":"Computational Molecular Biology: An Algorithmic Approach","author":"P.A. Pevzner","year":"2000","unstructured":"Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach. MIT Press, Cambridge (2000)"},{"issue":"1","key":"11_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.2000.2914","volume":"165","author":"G. Pighizzini","year":"2001","unstructured":"Pighizzini, G.: How hard is computing the edit distance? Information and Computation\u00a0165(1), 1\u201313 (2001)","journal-title":"Information and Computation"},{"key":"11_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BFb0036172","volume-title":"Fundamentals of Computation Theory","author":"D.A. Spielman","year":"1997","unstructured":"Spielman, D.A.: The complexity of error-correcting codes. In: Chlebus, B.S., Czaja, L. (eds.) FCT 1997. LNCS, vol.\u00a01279, pp. 67\u201384. Springer, Heidelberg (1997)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-24587-2_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,11,2]],"date-time":"2021-11-02T08:03:37Z","timestamp":1635840217000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-24587-2_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540206958","9783540245872"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-24587-2_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2003]]}}}