Optimal Spectral-Norm Approximate Minimization of Weighted Finite Automata

Abstract

This paper is concerned with the approximate minimization problem: to compute the best possible approximation of a weighted finite automaton given a bound on the number of states. The foundations of the work are grounded in the AAK theory, that we adapt to the framework of weighted automata over a one-letter alphabet. We provide theoretical guarantees and bounds on the quality of the approximation, in the spectral and $\ell^2$ norm. We develop an algorithm, based on the properties of Hankel operators, that returns the optimal approximation in the spectral norm for generative probabilistic automata.

Publications