[PDF][PDF] Optimal Approximate Minimization of One-Letter Weighted Finite Automata
arXiv preprint arXiv:2306.00135, 2023•claralacroce.github.io
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 …
(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 …
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 ℓ2 norm. Moreover, we provide a closed-form solution, and an algorithm, to compute the optimal approximation of a given size in polynomial time.
claralacroce.github.io
Showing the best result for this search. See all results