{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:09:42Z","timestamp":1725664182270},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540583257"},{"type":"electronic","value":"9783540486534"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1994]]},"DOI":"10.1007\/3-540-58325-4_194","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T15:44:09Z","timestamp":1330271049000},"page":"306-314","source":"Crossref","is-referenced-by-count":0,"title":["On the approximation of finding various minimal, maximal, and consistent sequences"],"prefix":"10.1007","author":[{"given":"Martin","family":"Middendorf","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"36_CR1","doi-asserted-by":"crossref","unstructured":"S. Arora, C. Lund, R. Motwani, R. Sundan, M. Szegedy, Proof verification and hardness of approximation problems, in: Proc. 33rd IEEE Symp. on Foundations of Computer Science (1992) 14\u201323.","DOI":"10.1109\/SFCS.1992.267823"},{"key":"36_CR2","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1016\/0304-3975(93)90167-R","volume":"119","author":"T. Jiang","year":"1993","unstructured":"T. Jiang, M. Li, On the complexity of learning strings and supersequences, Theoret. Comput. Sci.\n119 (1993) 336\u2013371.","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR3","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D. Maier","year":"1978","unstructured":"D. Maier, The complexity of some problems on subsequences and supersequences, J. ACM. 25 (1978), 322\u2013336.","journal-title":"J. ACM"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0304-3975(93)90200-D","volume":"108","author":"M. Middendorf","year":"1993","unstructured":"M. Middendorf, The shortest common nonsubsequence Problem is NP-complete, Theoret. Comput. Sci.\n108 (1993), 365\u2013369.","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, M. Yannakakis, Optimization, Approximation and Complexity Classes, 20th ACM Symp. on Theory of Computing, (1988) 229\u2013234.","DOI":"10.1145\/62212.62233"},{"key":"36_CR6","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"L. Pitt, L.G. Valiant, Computational limitations on learning from examples. J. ACM. 35 (1988) 965\u2013984.","journal-title":"J. ACM"},{"key":"36_CR7","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K.-J. R\u00e4ih\u00e4","year":"1981","unstructured":"K.-J. R\u00e4ih\u00e4, E. Ukkonen, The shortest common supersequence problem over binary alphabet is NP-complete. Theoret. Comput. Sci.\n16 (1981) 187\u2013198.","journal-title":"Theoret. Comput. Sci."},{"key":"36_CR8","doi-asserted-by":"crossref","first-page":"565","DOI":"10.1007\/BF01075212","volume":"25","author":"V. G. Timkovsky","year":"1990","unstructured":"V. G. Timkovsky, Complexity of common subsequence and supersequence problems and related problems, Cybernetics\n25 (1990), 565\u2013580.","journal-title":"Cybernetics"},{"key":"36_CR9","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L.G. Valiant","year":"1984","unstructured":"L.G. Valiant, A theory of the learnable. Comm. ACM.\n27 (1984) 1134\u20131142.","journal-title":"Comm. ACM."},{"key":"36_CR10","unstructured":"L. Zhang, The Approximation of Longest Common Non-Supersequences and Shortest Common Non-Subsequences is Hard, submitted for publication."}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-58325-4_194.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,28]],"date-time":"2021-04-28T01:13:38Z","timestamp":1619572418000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-58325-4_194"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994]]},"ISBN":["9783540583257","9783540486534"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/3-540-58325-4_194","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1994]]}}}