Minimization algorithms for sequential transducers

We present general algorithms for minimizing sequential finite-state transd ucers that output strings or numbers. The algorithms are shown to be effici ent since in the case of acyclic transducers and for output strings they op erate in O(S + \ E \ + \ V \ + (\ E \ - \ V \ + \ F \).(\ P-max\ + 1)) step s, where S is the sum of the lengths of all output labels of the resulting transducer, E the set of transitions of the given transducer, V the set of its states, F the set of final states, and P-max one of the longest of the longest common prefixes of the output paths leaving each state of the trans ducer. The algorithms apply to a larger class of transducers which includes subsequential transducers. (C) 2000 Elsevier Science B.V. All rights reser ved.