{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T03:33:14Z","timestamp":1752982394430,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662476659"},{"type":"electronic","value":"9783662476666"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-47666-6_10","type":"book-chapter","created":{"date-parts":[[2015,6,19]],"date-time":"2015-06-19T07:46:47Z","timestamp":1434700007000},"page":"121-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Edit Distance for Pushdown Automata"],"prefix":"10.1007","author":[{"given":"Krishnendu","family":"Chatterjee","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas A.","family":"Henzinger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rasmus","family":"Ibsen-Jensen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jan","family":"Otop","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,6,20]]},"reference":[{"key":"10_CR1","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1137\/0201022","volume":"1","author":"A Aho","year":"1972","unstructured":"Aho, A., Peterson, T.: A minimum distance error-correcting parser for context-free languages. SIAM J. of Computing 1, 305\u2013312 (1972)","journal-title":"SIAM J. of Computing"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Benedikt, M., Puppis, G., Riveros, C.: Regular repair of specifications. In: LICS 2011, pp. 335\u2013344 (2011)","DOI":"10.1109\/LICS.2011.43"},{"issue":"8","key":"10_CR3","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1016\/j.jcss.2013.06.001","volume":"79","author":"M Benedikt","year":"2013","unstructured":"Benedikt, M., Puppis, G., Riveros, C.: Bounded repairability of word languages. J. Comput. Syst. Sci. 79(8), 1302\u20131321 (2013)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"10_CR4","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"AK Chandra","year":"1981","unstructured":"Chandra, A.K., Kozen, D.C., Stockmeyer, L.J.: Alternation. J. ACM 28(1), 114\u2013133 (1981). http:\/\/doi.acm.org\/10.1145\/322234.322243","journal-title":"J. ACM"},{"key":"10_CR5","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Doyen, L., Henzinger, T.A.: Quantitative languages. ACM Trans. Comput. Log. 11(4) (2010)","DOI":"10.1145\/1805950.1805953"},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Ibsen-Jensen, R., Otop, J.: Edit distance for pushdown automata. CoRR abs\/1504.08259 (2015). http:\/\/arxiv.org\/abs\/1504.08259","DOI":"10.1007\/978-3-662-47666-6_10"},{"key":"10_CR7","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Henzinger, T.A., Otop, J.: Nested weighted automata. CoRR abs\/1504.06117 (2015). http:\/\/arxiv.org\/abs\/1504.06117 (to appear at LICS 2015)","DOI":"10.1109\/LICS.2015.72"},{"key":"10_CR8","doi-asserted-by":"crossref","unstructured":"Chatterjee, K., Ibsen-Jensen, R., Majumdar, R.: Edit distance for timed automata. In: HSCC 2014, pp. 303\u2013312 (2014)","DOI":"10.1145\/2562059.2562141"},{"key":"10_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/978-3-642-34109-0_24","volume-title":"String Processing and Information Retrieval","author":"P Gawrychowski","year":"2012","unstructured":"Gawrychowski, P.: Faster algorithm for computing the edit distance between SLP-compressed strings. In: Calder\u00f3n-Benavides, L., Gonz\u00e1lez-Caro, C., Ch\u00e1vez, E., Ziviani, N. (eds.) SPIRE 2012. LNCS, vol. 7608, pp. 229\u2013236. Springer, Heidelberg (2012)"},{"key":"10_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/978-3-642-40184-8_20","volume-title":"CONCUR 2013 \u2013 Concurrency Theory","author":"TA Henzinger","year":"2013","unstructured":"Henzinger, T.A., Otop, J.: From model checking to model measuring. In: D\u2019Argenio, P.R., Melgratti, H. (eds.) CONCUR 2013 \u2013 Concurrency Theory. LNCS, vol. 8052, pp. 273\u2013287. Springer, Heidelberg (2013)"},{"key":"10_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"JE Hopcroft","year":"1979","unstructured":"Hopcroft, J.E., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Adison-Wesley Publishing Company, Reading (1979)"},{"key":"10_CR12","doi-asserted-by":"crossref","unstructured":"Karp, R.: Mapping the genome: some combinatorial problems arising in molecular biology. In: STOC 93, pp. 278\u2013285. ACM (1993)","DOI":"10.1145\/167088.167170"},{"key":"10_CR13","first-page":"707","volume":"10","author":"VI Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet physics doklady. 10, 707\u2013710 (1966)","journal-title":"Soviet physics doklady."},{"key":"10_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1007\/978-3-540-73437-6_24","volume-title":"Combinatorial Pattern Matching","author":"Y Lifshits","year":"2007","unstructured":"Lifshits, Y.: Processing compressed texts: a tractability border. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, vol. 4580, pp. 228\u2013240. Springer, Heidelberg (2007)"},{"key":"10_CR15","doi-asserted-by":"publisher","first-page":"957","DOI":"10.1142\/S0129054103002114","volume":"14","author":"M Mohri","year":"2003","unstructured":"Mohri, M.: Edit-distance of weighted automata: general definitions and algorithms. Intl. J. of Foundations of Comp. Sci. 14, 957\u2013982 (2003)","journal-title":"Intl. J. of Foundations of Comp. Sci."},{"key":"10_CR16","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/TC.1976.5009232","volume":"25","author":"T Okuda","year":"1976","unstructured":"Okuda, T., Tanaka, E., Kasai, T.: A method for the correction of garbled words based on the levenshtein metric. IEEE Trans. Comput. 25, 172\u2013178 (1976)","journal-title":"IEEE Trans. Comput."},{"key":"10_CR17","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 165, 1\u201313 (2001)","journal-title":"Information and Computation"},{"key":"10_CR18","doi-asserted-by":"crossref","unstructured":"Saha, B.: The dyck language edit distance problem in near-linear time. In: FOCS 2014, pp. 611\u2013620 (2014)","DOI":"10.1109\/FOCS.2014.71"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages, and Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-47666-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,8]],"date-time":"2023-02-08T12:54:50Z","timestamp":1675860890000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-662-47666-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662476659","9783662476666"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-47666-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"20 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}