{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T16:10:05Z","timestamp":1790611805830,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642316524","type":"print"},{"value":"9783642316531","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-31653-1_9","type":"book-chapter","created":{"date-parts":[[2012,7,14]],"date-time":"2012-07-14T09:51:39Z","timestamp":1342259499000},"page":"85-96","source":"Crossref","is-referenced-by-count":5,"title":["Computing the Edit-Distance between a Regular Language and a Context-Free Language"],"prefix":"10.1007","author":[{"given":"Yo-Sub","family":"Han","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sang-Ki","family":"Ko","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kai","family":"Salomaa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"9_CR1","unstructured":"Allauzen, C., Mohri, M.: Linear-space computation of the edit-distance between a string and a finite automaton. In: London Algorithmics 2008: Theory and Practice. College Publications (2009)"},{"key":"9_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/978-3-642-22600-7_5","volume-title":"DCFS 2011","author":"L. Alpoge","year":"2011","unstructured":"Alpoge, L., Ang, T., Schaeffer, L., Shallit, J.: Decidability and Shortest Strings in Formal Languages. In: Holzer, M. (ed.) DCFS 2011. LNCS, vol.\u00a06808, pp. 55\u201367. Springer, Heidelberg (2011)"},{"key":"9_CR3","unstructured":"Bunke, H.: Edit distance of regular languages. In: Proceedings of 5th Annual Symposium on Document Analysis and Information Retrieval, pp. 113\u2013124 (1996)"},{"key":"9_CR4","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. Hopcroft","year":"1979","unstructured":"Hopcroft, J., Ullman, J.: Introduction to Automata Theory, Languages, and Computation, 2nd edn. Addison-Wesley, Reading (1979)","edition":"2"},{"key":"9_CR5","first-page":"293","volume":"9","author":"L. Kari","year":"2004","unstructured":"Kari, L., Konstantinidis, S.: Descriptional complexity of error\/edit systems. Journal of Automata, Languages and Combinatorics\u00a09, 293\u2013309 (2004)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"1307","DOI":"10.1016\/j.ic.2007.06.001","volume":"205","author":"S. Konstantinidis","year":"2007","unstructured":"Konstantinidis, S.: Computing the edit distance of a regular language. Information and Computation\u00a0205, 1307\u20131316 (2007)","journal-title":"Information and Computation"},{"issue":"8","key":"9_CR7","first-page":"707","volume":"10","author":"V.I. Levenshtein","year":"1966","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Soviet Physics Doklady\u00a010(8), 707\u2013710 (1966)","journal-title":"Soviet Physics Doklady"},{"key":"9_CR8","first-page":"321","volume":"7","author":"M. Mohri","year":"2002","unstructured":"Mohri, M.: Semiring frameworks and algorithms for shortest-distance problems. Journal of Automata, Languages and Combinatorics\u00a07, 321\u2013350 (2002)","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"6","key":"9_CR9","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. International Journal of Foundations of Computer Science\u00a014(6), 957\u2013982 (2003)","journal-title":"International Journal of Foundations of Computer Science"},{"key":"9_CR10","doi-asserted-by":"crossref","unstructured":"Pevzner, P.A.: Computational Molecular Biology: An Algorithmic Approach (Computational Molecular Biology). The MIT Press (2000)","DOI":"10.7551\/mitpress\/2022.001.0001"},{"issue":"1","key":"9_CR11","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":"9_CR12","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1145\/363347.363387","volume":"11","author":"K. Thompson","year":"1968","unstructured":"Thompson, K.: Programming techniques: Regular expression search algorithm. Communications of the ACM\u00a011, 419\u2013422 (1968)","journal-title":"Communications of the ACM"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1145\/360980.360995","volume":"17","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A.: Order-n correction for regular languages. Communications of the ACM\u00a017, 265\u2013268 (1974)","journal-title":"Communications of the ACM"},{"key":"9_CR14","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R.A. Wagner","year":"1974","unstructured":"Wagner, R.A., Fischer, M.J.: The string-to-string correction problem. Journal of the ACM\u00a021, 168\u2013173 (1974)","journal-title":"Journal of the ACM"},{"key":"9_CR15","unstructured":"Wood, D.: Theory of Computation. Harper & Row (1987)"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-31653-1_9.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T11:41:44Z","timestamp":1620128504000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-31653-1_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642316524","9783642316531"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-31653-1_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}