{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T01:44:31Z","timestamp":1768441471778,"version":"3.49.0"},"reference-count":13,"publisher":"World Scientific Pub Co Pte Lt","issue":"07","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>The edit-distance between two strings is the smallest number of operations required to transform one string into the other. The distance between languages L<jats:sub>1<\/jats:sub>and L<jats:sub>2<\/jats:sub>is the smallest edit-distance between string w<jats:sub>i<\/jats:sub>\u2208 L<jats:sub>i<\/jats:sub>, i = 1, 2. We consider the problem of computing the edit-distance of a given regular language and a given context-free language. First, we present an algorithm that finds for the languages an optimal alignment, that is, a sequence of edit operations that transforms a string in one language to a string in the other. The length of the optimal alignment, in the worst case, is exponential in the size of the given grammar and finite automaton. Then, we investigate the problem of computing only the edit-distance of the languages without explicitly producing an optimal alignment. We design a polynomial time algorithm that calculates the edit-distance based on unary homomorphisms.<\/jats:p>","DOI":"10.1142\/s0129054113400315","type":"journal-article","created":{"date-parts":[[2014,2,27]],"date-time":"2014-02-27T07:16:43Z","timestamp":1393485403000},"page":"1067-1082","source":"Crossref","is-referenced-by-count":21,"title":["THE EDIT-DISTANCE BETWEEN A REGULAR LANGUAGE AND A CONTEXT-FREE LANGUAGE"],"prefix":"10.1142","volume":"24","author":[{"given":"YO-SUB","family":"HAN","sequence":"first","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SANG-KI","family":"KO","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Yonsei University, 50, Yonsei-Ro, Seodaemun-Gu, Seoul 120-749, Korea"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KAI","family":"SALOMAA","sequence":"additional","affiliation":[{"name":"School of Computing, Queen's University, Kingston, Ontario K7L 3N6, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2014,2,26]]},"reference":[{"key":"p_3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00238-9"},{"key":"p_4","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.11.026"},{"issue":"2","key":"p_6","first-page":"293","volume":"9","author":"Kari L.","year":"2004","journal-title":"Languages and Combinatorics"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2007.06.001"},{"issue":"1","key":"p_8","first-page":"55","volume":"13","author":"Konstantinidis S.","year":"2008","journal-title":"Languages and Combinatorics"},{"issue":"4","key":"p_9","doi-asserted-by":"crossref","first-page":"257","DOI":"10.3233\/FI-2010-287","volume":"101","author":"Konstantinidis S.","year":"2010","journal-title":"Fundamenta Informaticae"},{"issue":"8","key":"p_10","first-page":"707","volume":"10","author":"Levenshtein V. I.","year":"1966","journal-title":"Soviet Physics Doklady"},{"key":"p_12","first-page":"321","volume":"7","author":"Mohri M.","year":"2002","journal-title":"Languages and Combinatorics"},{"key":"p_13","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002114"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2914"},{"key":"p_16","doi-asserted-by":"publisher","DOI":"10.1145\/363347.363387"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1145\/360980.360995"},{"key":"p_18","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054113400315","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,15]],"date-time":"2020-08-15T20:44:14Z","timestamp":1597524254000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054113400315"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":13,"journal-issue":{"issue":"07","published-online":{"date-parts":[[2014,2,26]]},"published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1142\/S0129054113400315"],"URL":"https:\/\/doi.org\/10.1142\/s0129054113400315","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]}}}