Logical Characterization of Bisimulation Metrics
arXiv:1610.08169 · doi:10.4204/EPTCS.227.4
Abstract
Bisimulation metrics provide a robust and accurate approach to study the behavior of nondeterministic probabilistic processes. In this paper, we propose a logical characterization of bisimulation metrics based on a simple probabilistic variant of the Hennessy-Milner logic. Our approach is based on the novel notions of mimicking formulae and distance between formulae. The former are a weak version of the well known characteristic formulae and allow us to characterize also (ready) probabilistic simulation and probabilistic bisimilarity. The latter is a 1-bounded pseudometric on formulae that mirrors the Hausdorff and Kantorovich lifting the defining bisimilarity pseudometric. We show that the distance between two processes equals the distance between their own mimicking formulae.
arXiv commentIn Proceedings QAPL'16, arXiv:1610.07696
References in corpus (9)
- Characterising Testing Preorders for Finite Probabilistic Processes
- Continuous Markovian Logics - Axiomatization and Quantified Metatheory
- Logical, Metric, and Algorithmic Characterisations of Probabilistic Bisimulation
- Game Refinement Relations and Metrics
- Fixed-point Characterization of Compositionality Properties of Probabilistic Processes Combinators
- Characterising Probabilistic Processes Logically
- Divide and Congruence II: From Decomposition of Modal Formulas to Preservation of Delay and Weak Bisimilarity
- Topologies of Stochastic Markov Models: Computational Aspects
- Modal Characterisations of Behavioural Pseudometrics
Cited by in corpus (7)
- SOS-based Modal Decomposition on Nondeterministic Probabilistic Processes
- Logical Characterization of Trace Metrics
- Trace and Testing Metrics on Nondeterministic Probabilistic Processes
- (Metric) Bisimulation Games and Real-Valued Modal Logics for Coalgebras
- Sound approximate and asymptotic probabilistic bisimulations for PCTL
- A van Benthem Theorem for Quantitative Probabilistic Modal Logic
- Quantitative Aspects of Programming Languages and Systems over the past years and beyond