Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kiefer, Stefan; Tang, Qiyi https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-155599
URL:

;

Approximate Bisimulation Minimisation

pdf-format:


Abstract

We propose polynomial-time algorithms to minimise labelled Markov chains whose transition probabilities are not known exactly, have been perturbed, or can only be obtained by sampling. Our algorithms are based on a new notion of an approximate bisimulation quotient, obtained by lumping together states that are exactly bisimilar in a slightly perturbed system. We present experiments that show that our algorithms are able to recover the structure of the bisimulation quotient of the unperturbed system.

BibTeX - Entry

@InProceedings{kiefer_et_al:LIPIcs.FSTTCS.2021.48,
  author =	{Kiefer, Stefan and Tang, Qiyi},
  title =	{{Approximate Bisimulation Minimisation}},
  booktitle =	{41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-215-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{213},
  editor =	{Boja\'{n}czy, Miko{\l}aj and Chekuri, Chandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/15559},
  URN =		{urn:nbn:de:0030-drops-155599},
  doi =		{10.4230/LIPIcs.FSTTCS.2021.48},
  annote =	{Keywords: Markov chains, Behavioural metrics, Bisimulation}
}

Keywords: Markov chains, Behavioural metrics, Bisimulation
Seminar: 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
Issue date: 2021
Date of publication: 29.11.2021
Supplementary Material: Software (Source Code): https://github.com/qiyitang71/approximate-quotienting archived at: https://archive.softwareheritage.org/swh:1:dir:42b8e694ce904b906e52bac502b425e424412461
Dataset (Experimental Results): https://bit.ly/3vcpblY


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI