Bisimulation Metrics for Weighted Automata
Pascale Gourdeau ( University of Oxford )
- 11:00 24th May 2018 ( week 5, Trinity Term 2018 )051
We develop a new bisimulation (pseudo)metric for weighted finite automata (WFA) that generalizes Boreale's linear bisimulation relation. Our metrics are induced by seminorms on the state space of WFA. Our development is based on spectral properties of sets of linear operators. In particular, the joint spectral radius of the transition matrices of WFA plays a central role. We also study continuity properties of the bisimulation pseudometric, establish an undecidability result for computing the metric, and give a preliminary account of applications to spectral learning of weighted automata.
Finally, we compare our metric to other bisimulation metrics in the special case of probabilistic automata.