A Canonical Form for Weighted Automata and Applications to Approximate Minimization

DOI10.1109/LICS.2015.70MaRDI QIDQ4635848zbMATH OpenFDO

Authors Borja Balle, Prakash Panangaden, Doina Precup

Publication date 23 April 2018

Published in 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Abstract: We study the problem of constructing approximations to a weighted automaton. Weighted finite automata (WFA) are closely related to the theory of rational series. A rational series is a function from strings to real numbers that can be computed by a finite WFA. Among others, this includes probability distributions generated by hidden Markov models and probabilistic automata. The relationship between rational series and WFA is analogous to the relationship between regular languages and ordinary automata. Associated with such rational series are infinite matrices called Hankel matrices which play a fundamental role in the theory of minimal WFA. Our contributions are: (1) an effective procedure for computing the singular value decomposition (SVD) of such infinite Hankel matrices based on their representation in terms of finite WFA; (2) a new canonical form for finite WFA based on this SVD decomposition; and, (3) an algorithm to construct approximate minimizations of a given WFA. The goal of our approximate minimization algorithm is to start from a minimal WFA and produce a smaller WFA that is close to the given one in a certain sense. The desired size of the approximating automaton is given as input. We give bounds describing how well the approximation emulates the behavior of the original WFA.

Recommendations

• Approximate minimization of weighted tree automata
• Morphisms and Minimisation of Weighted Automata
• Congruence and minimization of deterministic weighted finite automata
• Rigorous approximated determinization of weighted automata
• Minimal-determinization of weighted automaton
• An approximate determinization algorithm for weighted finite-state automata
• Minimizing Deterministic Weighted Tree Automata
• Minimizing deterministic weighted tree automata
• Hyper-minimisation of deterministic weighted finite automata over semifields
• On the minimization problem for \(\omega \)-automata

Cited in

(15)

• Generalization bounds for learning weighted automata
• On the metric-based approximate minimization of Markov chains
• Bisimulation metrics and norms for real-weighted automata
• Approximate minimization of weighted tree automata
• Learning infinite-word automata with loop-index queries
• Hankel matrices for weighted visibly pushdown automata
• Dimension-free concentration bounds on Hankel matrices for spectral learning
• On the Rademacher complexity of weighted automata
• Spectral learning of weighted automata. A forward-backward perspective
• scientific article; zbMATH DE number 7626702 (Why is no real title available?)
• Singular value automata and approximate minimization
• Approximate learning of limit-average automata
• Quantum theory in finite dimension cannot explain every general process with finite memory
• Optimal approximate minimization of one-letter weighted finite automata
• Optimal spectral-norm approximate minimization of weighted finite automata

This page was built for publication: A Canonical Form for Weighted Automata and Applications to Approximate Minimization

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