Singular value automata and approximate minimization

B Balle, P Panangaden, D Precup - Mathematical Structures in …, 2019 - cambridge.org
Mathematical Structures in Computer Science, 2019cambridge.org
The present paper uses spectral theory of linear operators to construct
approximatelyminimal realizations of weighted languages. Our new contributions are:(i) a
new algorithm for the singular value decomposition (SVD) decomposition of finite-rank
infinite Hankel matrices based on their representation in terms of weighted automata,(ii) a
new canonical form for weighted automata arising from the SVD of its corresponding
Hankelmatrix, and (iii) an algorithmto construct approximateminimizations of given weighted …
The present paper uses spectral theory of linear operators to construct approximatelyminimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for the singular value decomposition (SVD) decomposition of finite-rank infinite Hankel matrices based on their representation in terms of weighted automata, (ii) a new canonical form for weighted automata arising from the SVD of its corresponding Hankelmatrix, and (iii) an algorithmto construct approximateminimizations of given weighted automata by truncating the canonical form.We give bounds on the quality of our approximation.
Cambridge University Press
Showing the best result for this search. See all results