Minimization algorithms for sequential transducers

We present general algorithms for minimizing sequential finite-state transducers that output strings or numbers. The algorithms are shown to be efficient since in the case of acyclic transducers and for output strings they operate in O(S+|E|+|V|+(|E|−|V|+|F|)·(|P max |+1)) steps, 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 transducer. The algorithms apply to a larger class of transducers which includes subsequential transducers.

Authors

• Mehryar Mohri

Keywords

• Finite automata
• Finite-state transducers
• Rational power series
• Semiring
• Shortest-paths algorithms