{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T06:29:41Z","timestamp":1768976981312,"version":"3.49.0"},"reference-count":12,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>Composition of weighted transducers is a fundamental algorithm used in many applications, including for computing complex edit-distances between automata, or string kernels in machine learning, or to combine different components of a speech recognition, speech synthesis, or information extraction system. We present a generalization of the composition of weighted transducers, n-way composition, which is dramatically faster in practice than the standard composition algorithm when combining more than two transducers. The worst-case complexity of our algorithm for composing three transducers T<jats:sub>1<\/jats:sub>, T<jats:sub>2<\/jats:sub>, and T<jats:sub>3<\/jats:sub>resulting in T, is O(|T|<jats:sub>Q<\/jats:sub>min (d(T<jats:sub>1<\/jats:sub>)d(T<jats:sub>3<\/jats:sub>), d(T<jats:sub>2<\/jats:sub>)) + |T|<jats:sub>E<\/jats:sub>), where |\u00b7|<jats:sub>Q<\/jats:sub>denotes the number of states, |\u00b7|<jats:sub>E<\/jats:sub>the number of transitions, and d(\u00b7) the maximum out-degree. As in regular composition, the use of perfect hashing requires a pre-processing step with linear-time expected complexity in the size of the input transducers. In many cases, this approach significantly improves on the complexity of standard composition. Our algorithm also leads to a dramatically faster composition in practice. Furthermore, standard composition can be obtained as a special case of our algorithm. We report the results of several experiments demonstrating this improvement. These theoretical and empirical improvements significantly enhance performance in the applications already mentioned.<\/jats:p>","DOI":"10.1142\/s0129054109006772","type":"journal-article","created":{"date-parts":[[2009,7,29]],"date-time":"2009-07-29T11:44:22Z","timestamp":1248867862000},"page":"613-627","source":"Crossref","is-referenced-by-count":6,"title":["<font>N<\/font>-WAY COMPOSITION OF WEIGHTED FINITE-STATE TRANSDUCERS"],"prefix":"10.1142","volume":"20","author":[{"given":"CYRIL","family":"ALLAUZEN","sequence":"first","affiliation":[{"name":"Google Research, 76 Ninth Avenue, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MEHRYAR","family":"MOHRI","sequence":"additional","affiliation":[{"name":"Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, NY 10012, USA"},{"name":"Google Research, 76 Ninth Avenue, New York, NY 10011, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-663-09367-1"},{"key":"rf3","first-page":"1035","volume":"5","author":"Cortes Corinna","journal-title":"Journal of Machine Learning Research"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-59126-6_10"},{"key":"rf5","unstructured":"Samuel\u00a0Eilenberg, Automata, Languages and Machines (Academic Press)\u00a0pp. 1974\u20131976."},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1987.1165125"},{"key":"rf7","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-69959-7","volume-title":"Automata, Languages","author":"Kuich Werner","year":"1986"},{"key":"rf8","volume":"23","author":"Mohri Mehryar","journal-title":"Computational Linguistics"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002114"},{"key":"rf10","volume-title":"Applied Combinatorics on Words","author":"Mohri Mehryar","year":"2005"},{"key":"rf12","series-title":"chapter Speech Recognition by Composition of Weighted Finite Automata","volume-title":"Finite State Language Processing","author":"Pereira Fernando","year":"1997"},{"key":"rf13","series-title":"Cambridge Mathematical Library","volume-title":"Combinatorics on words","author":"Perrin Dominique","year":"1997"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-6264-0"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054109006772","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,15]],"date-time":"2024-03-15T15:02:28Z","timestamp":1710514948000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054109006772"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":12,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1142\/S0129054109006772"],"URL":"https:\/\/doi.org\/10.1142\/s0129054109006772","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}