Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains

Timm SporkTimm Spork, Christel BaierChristel Baier, Joost-Pieter KatoenJoost-Pieter Katoen, Sascha KlüppelholzSascha Klüppelholz, Jakob PiribauerJakob Piribauer

Timm Spork, Christel Baier, Joost-Pieter Katoen, Sascha Klüppelholz, Jakob Piribauer
Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains
In Ruzica Piskac, Zvonimir Rakamarić, eds., Proceedings of the 37th International Conference on Computer Aided Verification (CAV2025), Part II, volume 15932 of Lecture Notes in Computer Science (LNCS), 56-81, July 2025. Springer

Details
Bibtex

KurzfassungAbstract
We introduce (ε, δ)-bisimulation, a novel type of approximate probabilistic bisimulation for continuous-time Markov chains. In contrast to related notions, (ε, δ)-bisimulation allows the use of different tolerances for the transition probabilities (ε, additive) and total exit rates (δ, multiplicative) of states. Fundamental properties of the notion, as well as bounds on the absolute difference of time- and reward-bounded reachability probabilities for (ε,δ)-bisimilar states, are established.
Projekt:Project: CPEC, CeTI
Forschungsgruppe:Research Group: Algebraische und logische Grundlagen der InformatikAlgebraic and Logical Foundations of Computer Science

The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-031-98679-6_3.

@inproceedings{SBKKP2025,
  author    = {Timm Spork and Christel Baier and Joost-Pieter Katoen and Sascha
               Kl{\"{u}}ppelholz and Jakob Piribauer},
  title     = {Approximate Probabilistic Bisimulation for Continuous-Time Markov
               Chains},
  editor    = {Ruzica Piskac and Zvonimir Rakamari{\'{c}}},
  booktitle = {Proceedings of the 37th International Conference on Computer
               Aided Verification (CAV2025), Part {II}},
  series    = {Lecture Notes in Computer Science (LNCS)},
  volume    = {15932},
  publisher = {Springer},
  year      = {2025},
  month     = {July},
  pages     = {56-81},
  doi       = {10.1007/978-3-031-98679-6_3}
}