DROPS

Document

DOI: 10.4230/LIPIcs.ICALP.2017.103

Bisimulation Metrics for Weighted Automata

Authors: Borja Balle, Pascale Gourdeau, and Prakash Panangaden

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract

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.

Cite as

Borja Balle, Pascale Gourdeau, and Prakash Panangaden. Bisimulation Metrics for Weighted Automata. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 103:1-103:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{balle_et_al:LIPIcs.ICALP.2017.103,
  author =	{Balle, Borja and Gourdeau, Pascale and Panangaden, Prakash},
  title =	{{Bisimulation Metrics for Weighted Automata}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{103:1--103:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.103},
  URN =		{urn:nbn:de:0030-drops-73959},
  doi =		{10.4230/LIPIcs.ICALP.2017.103},
  annote =	{Keywords: weighted automata, bisimulation, metrics, spectral theory, learning}
}

Search Results

Documents authored by Gourdeau, Pascale

Bisimulation Metrics for Weighted Automata

Abstract

Cite as

Thanks for your feedback!

Could not send message