Conference item
Approximate bisimulation minimisation
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, pdf, 791.3KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.FSTTCS.2021.48
Authors
- Publisher:
- Schloss Dagstuhl
- Host title:
- 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021)
- Volume:
- 213
- Pages:
- 48:1--48:16
- Series:
- Leibniz International Proceedings in Informatics
- Publication date:
- 2021-11-29
- Acceptance date:
- 2021-09-20
- Event title:
- 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
- Event location:
- Virtual event
- Event website:
- https://www.fsttcs.org.in/2021/
- Event start date:
- 2021-12-15
- Event end date:
- 2021-12-17
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 978-3-95977-215-0
- Language:
-
English
- Keywords:
- Pubs id:
-
1198836
- Local pid:
-
pubs:1198836
- Deposit date:
-
2021-10-05
- ARK identifier:
Terms of use
- Copyright holder:
- Kiefer and Tang.
- Copyright date:
- 2021
- Rights statement:
- © Stefan Kiefer and Qiyi Tang; licensed under Creative Commons License CC-BY 4.0
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record