Approximate Probabilistic Bisimulation for Continuous-Time Markov Chains

2025/05/21 by Spork, Timm, Baier, Christel, Katoen, Joost-Pieter +2
#FOS: Computer and information sciences #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.2505.15587

Abstract

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.

Related

• A Spectrum of Approximate Probabilistic Bisimulations
• Probabilistic Bisimulation: Naturally on Distributions
• Two behavioural pseudometrics for continuous-time Markov processes
• On the Relationship between Bisimulation and Trace Equivalence in an Approximate Probabilistic Context (Extended Version)
• Robust Probabilistic Bisimilarity for Labelled Markov Chains