[BFKP25]
Franck van Breugel, Syyeda Zainab Fatmi, Stefan Kiefer and David Parker.
Robust Probabilistic Bisimilarity for Labelled Markov Chains.
In Proc. 37th International Conference on Computer Aided Verification (CAV'25), Springer. To appear.
July 2025.
[pdf]
[bib]
[Proposes a notion of robust probabilistic bisimulation, and a minimisation algorithm implemented in PRISM.]
|
Notes:
The original publication is available at link.springer.com.
|
Links:
[Google]
[Google Scholar]
|
Abstract.
Despite its prevalence, probabilistic bisimilarity suffers from
a lack of robustness under minuscule perturbations of the transition probabilities. This can lead to discontinuities in the probabilistic bisimilarity distance function, undermining its reliability in practical applications where transition probabilities are often approximations derived from experimental data. Motivated by this limitation, we introduce the notion of robust probabilistic bisimilarity for labelled Markov chains, which ensures the continuity of the probabilistic bisimilarity distance function. We also propose an efficient algorithm for computing robust probabilistic bisimilarity and show that it performs well in practice, as evidenced by our experimental results.
|