文章基本信息

标题：Bisimulation Metrics for Weighted Automata
本地全文：下载
作者：Borja Balle ; Pascale Gourdeau ; Prakash Panangaden 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：80
页码：103:1-103:14
DOI：10.4230/LIPIcs.ICALP.2017.103
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：weighted automata; bisimulation; metrics; spectral theory; learning