1. A method of adding a new sentence to a word-level finite state transducer (FST) having a plurality of states and connecting arcs, the method comprising: determining an existing prefix subset of states and arcs in the FST matching a prefix portion of the new sentence; appending a new sequence of states and arcs to the FST corresponding to a remainder of the new sentence after the prefix portion; determining an existing suffix subset of states and arcs in the FST corresponding to a suffix portion of the new sentence; and connecting the portion of the new sequence before the suffix portion to the suffix subset to create a modified FST including the new sentence and not satisfying global optimization criteria.