Paper: Simpler And More General Minimization For Weighted Finite-State Automata

ACL ID N03-1009
Title Simpler And More General Minimization For Weighted Finite-State Automata
Venue Human Language Technologies
Session Main Conference
Year 2003
Authors

Previous work on minimizing weighted finite-state automata (including transducers) is limited to particular types of weights. We present efficient new minimization algorithms that apply much more generally, while being simpler and about as fast. We also point out theoretical limits on minimization algo- rithms. We characterize the kind of “well-behaved” weight semirings where our methods work. Outside these semirings, minimization is not well-defined (in the sense of producing a unique minimal automaton), and even finding the minimum number of states is in general NP-complete and inapproximable.