Optimal Approximate Minimization of One-Letter Weighted Finite Automata
arXiv:2306.00135 · doi:10.1017/S0960129524000276
Abstract
In this paper, we study the approximate minimization problem of weighted finite automata (WFAs): to compute the best possible approximation of a WFA given a bound on the number of states. By reformulating the problem in terms of Hankel matrices, we leverage classical results on the approximation of Hankel operators, namely the celebrated Adamyan-Arov-Krein (AAK) theory. We solve the optimal spectral-norm approximate minimization problem for irredundant WFAs with real weights, defined over a one-letter alphabet. We present a theoretical analysis based on AAK theory, and bounds on the quality of the approximation in the spectral norm and norm. Moreover, we provide a closed-form solution, and an algorithm, to compute the optimal approximation of a given size in polynomial time.
32 pages. arXiv admin note: substantial text overlap with arXiv:2102.06860
References in corpus (6)
- Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
- Learning Deterministic Weighted Automata with Queries and Counterexamples
- Singular value automata and approximate minimization
- Hardy-space function theory, operator model theory, and dissipative linear systems: the multivariable, free-noncommutative, weighted Bergman-space setting
- Extracting Weighted Automata for Approximate Minimization in Language Modelling
- Towards an AAK Theory Approach to Approximate Minimization in the Multi-Letter Case