Language Equivalence from Nondeterministic to Weighted Automata—and Back

Language equivalence is closely related to Rocco De Nicola’s contributions to concurrency theory. Here we study language equivalence and state reduction for Nondeterministic Finite Automata (NFAs). We work in a linear algebraic setting based on Weighted Automata (WAs) and with a focus on algorithmic aspects. We start from the classic projection-based minimization algorithm for WAs with weights in a field. We analyse the reasons for the failure of this algorithm, in both a theoretical and a practical perspective, when transferred to the poorer algebraic setting of Boolean WAs, that is NFAs. This analysis suggests a different construction based on quotients and an ensuing algorithm applicable to NFAs. Although this algorithm does  not achieve NFAs minimization in general, it is quite effective at state reduction in a practical perspective. Additionally, we show that its linear algebraic formulation is amenable to an efficient vectorized implementation, and discuss the resulting empirical complexity. Experiments conducted with a proof-of-concept implementation of this algorithm across a variety of benchmarks show promising results in comparison to a state-of-the-art tool for NFAs state reduction.