{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,22]],"date-time":"2025-03-22T04:20:03Z","timestamp":1742617203623,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":22,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540602491"},{"type":"electronic","value":"9783540447702"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1995]]},"DOI":"10.1007\/3-540-60249-6_70","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T17:58:02Z","timestamp":1330279082000},"page":"383-392","source":"Crossref","is-referenced-by-count":0,"title":["How hard is to compute the edit distance"],"prefix":"10.1007","author":[{"given":"Giovanni","family":"Pighizzini","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,5,30]]},"reference":[{"key":"33_CR1","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/BF01275489","volume":"3","author":"E. Allender","year":"1993","unstructured":"E. Allender, D. Bruschi, and G. Pighizzini. The complexity of computing maximal word functions. Computational Complexity, 3:368\u2013391, 1993.","journal-title":"Computational Complexity"},{"key":"33_CR2","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1109\/TASSP.1980.1163382","volume":"28","author":"M. Ackroyd","year":"1980","unstructured":"M. Ackroyd. Isolated word recognition using the weighted Levenshtein distance. IEEE Transactions on Acoustics, Speech and Signal Processing, 28:243\u2013244, 1980.","journal-title":"IEEE Transactions on Acoustics, Speech and Signal Processing"},{"key":"33_CR3","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/BF01840365","volume":"2","author":"A. Apostolico","year":"1987","unstructured":"A. Apostolico and C. Guerra. The longest common subsequence problem revisited. Algorithmica, 2:315\u2013336, 1987.","journal-title":"Algorithmica"},{"doi-asserted-by":"crossref","unstructured":"E. Allender and J. Jiao. Depth reduction for noncommutative arithmetic circuits. In Proc. 25th ACM Symposium on Theory of Computing, pages 515\u2013522, 1993.","key":"33_CR4","DOI":"10.1145\/167088.167226"},{"key":"33_CR5","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0304-3975(93)90252-O","volume":"107","author":"C. \u00c0lvarez","year":"1993","unstructured":"C. \u00c0lvarez and B. Jenner. A very hard log-space counting class. Theoretical Computer Science, 107:3\u201330, 1993.","journal-title":"Theoretical Computer Science"},{"key":"33_CR6","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"A. Aho","year":"1972","unstructured":"A. Aho and T. Peterson. A minimum distance error-correcting parser for context-free languages. SIAM J. Computing, 1:305\u2013312, 1972.","journal-title":"SIAM J. Computing"},{"unstructured":"R. Bellman. Dynamic Programming. Princeton Univ. Press, 1957.","key":"33_CR7"},{"key":"33_CR8","first-page":"133","volume":"48","author":"F. Brandenburg","year":"1977","unstructured":"F. Brandenburg. On one-way auxiliary pushdown automata. In Proc. 3rd GI Conference, Lecture Notes in Computer Science 48, pages 133\u2013144, 1977.","journal-title":"Lecture Notes in Computer Science"},{"key":"33_CR9","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S. Cook","year":"1971","unstructured":"S. Cook. Characterization of pushdown machines in terms of time-bounded computers. Journal of the ACM, 18:4\u201318, 1971.","journal-title":"Journal of the ACM"},{"key":"33_CR10","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/S0019-9958(85)80041-3","volume":"64","author":"S. Cook","year":"1985","unstructured":"S. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64:2\u201322, 1985.","journal-title":"Information and Control"},{"doi-asserted-by":"crossref","unstructured":"D. Eppstein, Z. Galil, and R. Giancarlo. Efficient algorithms with applications to molecular biology. In R. Capocelli, editor, Sequences, pages 59\u201374. Springer-Verlag, 1990.","key":"33_CR11","DOI":"10.1007\/978-1-4612-3352-7_5"},{"key":"33_CR12","volume-title":"Introduction to automata theory, languages, and computations","author":"J. Hopcroft","year":"1979","unstructured":"J. Hopcroft and J. Ullman. Introduction to automata theory, languages, and computations. Addison-Wesley, Reading, MA, 1979."},{"key":"33_CR13","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF02090763","volume":"23","author":"D. Huynh","year":"1990","unstructured":"D. Huynh. The complexity of ranking simple languages. Mathematical Systems Theory, 23:1\u201319, 1990.","journal-title":"Mathematical Systems Theory"},{"key":"33_CR14","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1142\/S0129054191000121","volume":"2","author":"D. Huynh","year":"1991","unstructured":"D. Huynh. Efficient detectors and constructors for simple languages. International Journal of Foundations of Computer Science, 2:183\u2013205, 1991.","journal-title":"International Journal of Foundations of Computer Science"},{"doi-asserted-by":"crossref","unstructured":"R. Karp. Mapping the genome: some combinatorial problems arising in molecular biology. In Proc. 25th ACM Symposium on Theory of Computing, pages 278\u2013285, 1993.","key":"33_CR15","DOI":"10.1145\/167088.167170"},{"key":"33_CR16","first-page":"707","volume":"10","author":"V. Levenshtein","year":"1966","unstructured":"V. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics-Doklady, 10:707\u2013710, 1966.","journal-title":"Soviet Physics-Doklady"},{"key":"33_CR17","doi-asserted-by":"crossref","first-page":"687","DOI":"10.1137\/0217044","volume":"17","author":"G. Miller","year":"1988","unstructured":"G. Miller, V. Ramachandran, and E. Kaltofen. Efficient parallel evaluation of straight-line code and arithmetic circuits. SIAM J. Computing, 17:687\u2013695, 1988.","journal-title":"SIAM J. Computing"},{"key":"33_CR18","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1109\/TC.1976.5009232","volume":"25","author":"T. Okuda","year":"1976","unstructured":"T. Okuda, E. Tanaka, and T. Kasai. A method for the correction of garbled words based on the Levenshtein metric. IEEE Transactions on Computers, 25:172\u2013178, 1976.","journal-title":"IEEE Transactions on Computers"},{"unstructured":"G. Pighizzini. A parallel minimum distance error-correcting context-free parser. In Theoretical Computer Science \u2014 Proceedings of the Fourth Italian Conference, pages 305\u2013316. World Scientific, 1992.","key":"33_CR19"},{"key":"33_CR20","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1016\/0196-6774(81)90010-9","volume":"2","author":"Y. Shiloach","year":"1981","unstructured":"Y. Shiloach and U. Vishkin. Finding the maximum, merging and sorting in a parallel computation model. Journal of Algorithms, 2:88\u2013102, 1981.","journal-title":"Journal of Algorithms"},{"doi-asserted-by":"crossref","unstructured":"V. Vinaj. Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits. In Proc. 6th Structure in Complexity Theory, pages 270\u2013284, 1991.","key":"33_CR21","DOI":"10.1109\/SCT.1991.160269"},{"key":"33_CR22","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"R. Wagner and M. Fisher. The string-to-string correction problem. Journal of the ACM, 21:168\u2013173, 1974.","journal-title":"Journal of the ACM"}],"container-title":["Lecture Notes in Computer Science","Fundamentals of Computation Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-60249-6_70.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T22:56:47Z","timestamp":1742597807000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-60249-6_70"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995]]},"ISBN":["9783540602491","9783540447702"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/3-540-60249-6_70","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1995]]}}}