2026-07-23T20:44:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7395 2024-03-06T10:40:29Z ddc:004 open_access

Bisimulation Metrics for Weighted Automata Balle, Borja Gourdeau, Pascale Panangaden, Prakash weighted automata bisimulation metrics spectral theory learning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Borja Balle and Pascale Gourdeau and Prakash Panangaden 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.103 urn:nbn:de:0030-drops-73959 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.103 eng https://creativecommons.org/licenses/by/3.0/legalcode