{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,15]],"date-time":"2026-01-15T05:25:00Z","timestamp":1768454700225,"version":"3.49.0"},"reference-count":33,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,12]]},"abstract":"<jats:p> The problem of computing the similarity between two sequences arises in many areas such as computational biology and natural language processing. A common measure of the similarity of two strings is their edit-distance, that is the minimal cost of a series of symbol insertions, deletions, or substitutions transforming one string into the other. In several applications such as speech recognition or computational biology, the objects to compare are distributions over strings, i.e., sets of strings representing a range of alternative hypotheses with their associated weights or probabilities. We define the edit-distance of two distributions over strings and present algorithms for computing it when these distributions are given by automata. In the particular case where two sets of strings are given by unweighted automata, their edit-distance can be computed using the general algorithm of composition of weighted transducers combined with a single-source shortest-paths algorithm. In the general case, we show that general weighted automata algorithms over the appropriate semirings can be used to compute the edit-distance of two weighted automata exactly. These include classical algorithms such as the composition and \u220a-removal of weighted transducers and a new and simple synchronization algorithm for weighted transducers which, combined with \u220a-removal, can be used to normalize weighted transducers with bounded delays. Our algorithm for computing the edit-distance of weighted automata can be used to improve the word accuracy of automatic speech recognition systems. It can also be extended to provide an edit-distance automaton useful for re-scoring and other post-processing purposes in the context of large-vocabulary speech recognition. <\/jats:p>","DOI":"10.1142\/s0129054103002114","type":"journal-article","created":{"date-parts":[[2003,12,19]],"date-time":"2003-12-19T05:51:21Z","timestamp":1071813081000},"page":"957-982","source":"Crossref","is-referenced-by-count":62,"title":["EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS"],"prefix":"10.1142","volume":"14","author":[{"given":"MEHRYAR","family":"MOHRI","sequence":"first","affiliation":[{"name":"AT&amp;T Labs \u2013 Research, 180 Park Avenue,  Rm E135, Florham Park, NJ 07932, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume":"8","author":"Allauzen C.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2000111"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-73235-5"},{"key":"rf6","volume-title":"Introduction to Algorithms","author":"Cormen T.","year":"1992"},{"key":"rf8","first-page":"273","volume":"20","author":"Cortes C.","journal-title":"Machine Learning"},{"key":"rf10","volume-title":"Text Algorithms","author":"Crochemore M.","year":"1994"},{"key":"rf11","volume":"1","author":"Dijkstra E. W.","journal-title":"Numerische Mathematik"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492"},{"key":"rf13","volume-title":"Automata, Languages and Machines","author":"Eilenberg S.","year":"1974"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90230-Q"},{"key":"rf15","doi-asserted-by":"publisher","DOI":"10.1137\/0219067"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931"},{"key":"rf18","volume-title":"Introduction to Formal Language Theory","author":"Harrison M. A.","year":"1978"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-69959-7"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"rf23","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"rf24","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E. L.","year":"1976"},{"key":"rf25","first-page":"707","volume":"10","author":"Levenshtein V. I.","journal-title":"Soviet Physics - Doklady"},{"key":"rf26","doi-asserted-by":"publisher","DOI":"10.1006\/csla.2000.0152"},{"key":"rf27","first-page":"2","volume":"23","author":"Mohri M.","journal-title":"Computational Linguistics"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054102000996"},{"key":"rf29","first-page":"321","volume":"7","author":"Mohri M.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf32","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00014-6"},{"key":"rf34","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840446"},{"key":"rf35","unstructured":"F. C. N.\u00a0Pereira and M. D.\u00a0Riley, Finite-State Language Processing, eds. E.\u00a0Roche and Y.\u00a0Schabes (MIT Press, Cambridge, Massachusetts, 1997)\u00a0pp. 431\u2013453."},{"key":"rf36","doi-asserted-by":"publisher","DOI":"10.1109\/34.682181"},{"key":"rf37","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0"},{"key":"rf38","volume":"4","author":"Sch\u00fctzenberger M. P.","journal-title":"Information and Control"},{"key":"rf39","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(77)90055-X"},{"key":"rf41","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"rf42","volume-title":"Statistical Learning Theory","author":"Vapnik V. N.","year":"1998"},{"key":"rf43","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\/S0129054103002114","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:25:41Z","timestamp":1565191541000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103002114"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,12]]},"references-count":33,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,12]]}},"alternative-id":["10.1142\/S0129054103002114"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103002114","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,12]]}}}