REPORT cheng:rr06-62/IDIAP A Generalized Dynamic Composition Algorithm of Weighted Finite State Transducers for Large Vocabulary Speech Recognition Cheng, Octavian Dines, John Magimai-Doss, Mathew EXTERNAL http://publications.idiap.ch/attachments/reports/2006/cheng-idiap-rr-06-62.pdf PUBLIC Idiap-RR-62-2006 2006 IDIAP Submitted for publication We propose a generalized dynamic composition algorithm of weighted finite state transducers (WFST,',','), which avoids the creation of non-coaccessible paths, performs weight look-ahead and does not impose any constraints to the topology of the WFSTs. Experimental results on Wall Street Journal (WSJ1) 20k-word trigram task show that at 17\% WER (moderately-wide beam width,',','), the decoding time of the proposed approach is about 48\% and 65\% of the other two dynamic composition approaches. In comparison with static composition, at the same level of 17\% WER, we observe a reduction of about 60\% in memory requirement, with an increase of about 60\% in decoding time due to extra overheads for dynamic composition.