Creative Commons Attribution 4.0 license (CC BY 4.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2021.48
URN: urn:nbn:de:0030-drops-155599
URL: https://drops.dagstuhl.de/opus/volltexte/2021/15559/
Kiefer, Stefan ; Tang, Qiyi
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 |
