Simpler and More General Minimization for Weighted Finite-State Automata

Jason EisnerNAACL 2003 · OpenReview

Abstract

Previous work on minimizing weighted finite-state automata (WFSA) 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 characterize the "well-behaved" weight semirings where our methods work and demonstrate that outside these semirings, minimization is not well-defined or is NP-complete.

Introduction

Finite-state automata (FSA) and transducers are foundational tools in natural language processing (NLP) and speech recognition. Minimizing these automata—reducing them to the smallest possible number of states and transitions—is crucial for saving memory and speeding up computations. While minimizing unweighted automata is a solved problem, minimizing weighted automata (WFSA) is significantly more complex. Previous algorithms were restricted to specific weight types and relied on complex operations to extract common factors across all possible paths.

Theoretical Bounds and Complexity

A major contribution of this work is identifying the mathematical boundaries of minimization. We prove that finding the minimum number of states for a WFSA over an arbitrary semiring is NP-complete. Furthermore, we show that in certain mathematical structures, such as the semiring $\mathbb{Z}[\sqrt{-5}]$, unique minimization is not even well-defined because weights can be factored in multiple, incompatible ways.

Extracted figure from page 3 of Simpler and More General Minimization for Weighted Finite-State Automata

A Simpler Pushing Algorithm

For "division semirings"—where weights have inverses, such as real numbers or additive systems—we introduce a radically simpler pushing method. Instead of the complex task of finding a common factor for all infinitely many paths leaving a state, our algorithm simply identifies the lexicographically shortest path to a final state. By factoring out the weight of just this single path and pushing it backward, we can canonicalize the automaton in linear time, $O(|states| + t \cdot |arcs|)$.

The Inverse Letter Trick

To extend these benefits to non-division semirings, such as string transducers, we employ an "inverse letter" trick. By temporarily embedding the weights into a larger space that includes formal inverses (e.g., treating a string $x$ as having an inverse $x^{-1}$), we can apply our fast division-based pushing algorithm.

Figure 4: A WFSA using formal inverse letters to facilitate pushing in non-division semirings.

Once the weights are pushed, the inverse elements are shifted forward until they cancel out, leaving a minimized automaton. While this doesn't always yield a strict canonical form, it effectively minimizes the state count, making it highly practical for real-world applications.

Conclusion

This research simplifies and generalizes the process of WFSA minimization. By moving away from global path aggregation toward a shortest-path approach and utilizing formal inverses, we enable efficient optimization for a wider variety of models. These advancements pave the way for more memory-efficient and faster machine learning pipelines on constrained devices.

Summary updated

Abstract

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 algorithms. 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.
BibTeX
@inproceedings{eisner2003simpler,
  author = {Jason Eisner},
  title = {{Simpler and More General Minimization for Weighted Finite-State Automata}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2003},
  url = {https://openreview.net/forum?id=Hy-WNXZ_WB},
}
Figure