Singular value automata and approximate minimization

DOI10.1017/S0960129519000094MaRDI QIDQ5108539zbMATH OpenWikidataFDO

Authors Borja Balle, Prakash Panangaden, Doina Precup

Publication date 4 May 2020

Published in Mathematical Structures in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.05994

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Factorization of matrices (15A23) Toeplitz operators, Hankel operators, Wiener-Hopf operators (47B35) Formal languages and automata (68Q45)

Abstract: The present paper uses spectral theory of linear operators to construct approximately minimal realizations of weighted languages. Our new contributions are: (i) a new algorithm for the SVD decomposition of 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 Hankel matrix and (iii) an algorithm to construct approximate minimizations of given weighted automata by truncating the canonical form. We give bounds on the quality of our approximation.

Recommendations

• A Canonical Form for Weighted Automata and Applications to Approximate Minimization
• Approximate minimization of weighted tree automata
• Stability and Complexity of Minimising Probabilistic Automata
• An approximate determinization algorithm for weighted finite-state automata
• Unweighted and weighted hyper-minimization

Cites work

• A Canonical Form for Weighted Automata and Applications to Approximate Minimization
• A coalgebraic perspective on linear weighted automata
• A spectral algorithm for learning hidden Markov models
• Algebra-coalgebra duality in Brzozowski's minimization algorithm
• All optimal Hankel-norm approximations of linear multivariable systems and theirL,^∞-error bounds†
• Applications of weighted automata in natural language processing
• Approximating labelled Markov processes
• Approximation of Large-Scale Dynamical Systems
• Bisimulation metrics for weighted automata
• Convergence Rates for Markov Chains
• Digital image compression
• scientific article; zbMATH DE number 47946 (Why is no real title available?)
• scientific article; zbMATH DE number 3567782 (Why is no real title available?)
• scientific article; zbMATH DE number 1012640 (Why is no real title available?)
• scientific article; zbMATH DE number 1875877 (Why is no real title available?)
• scientific article; zbMATH DE number 3384830 (Why is no real title available?)
• scientific article; zbMATH DE number 3189697 (Why is no real title available?)
• Minimization via duality
• Model checking linear-time properties of probabilistic systems
• Multivariable Nehari problem and interpolation.
• Noncommutative rational series with applications
• On rational stochastic languages
• Simple spectral bounds for sums of certain Kronecker products
• Spectral learning of weighted automata. A forward-backward perspective
• Stability and Complexity of Minimising Probabilistic Automata
• Weighted Bisimulation in Linear Algebraic Form

Cited in

(4)

• Bisimulation metrics and norms for real-weighted automata
• Approximate minimization of weighted tree automata
• Optimal approximate minimization of one-letter weighted finite automata
• Optimal spectral-norm approximate minimization of weighted finite automata

This page was built for publication: Singular value automata and approximate minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5108539)