The Metric Analogue of Weak Bisimulation for Probabilistic Processes.
Josée Desharnais, Vineet Gupta, Radha Jagadeesan, Prakash Panangaden
Abstract
We observe that equivalence is not a robust concept in the
presence of numerical information - such as probabilities - in the
model. We develop a metric analogue of weak bisimulation in the
spirit of our earlier work on metric analogues for strong
bisimulation. We give a fixed point characterization of the
metric. This makes available coinductive reasoning principles and
allows us to prove metric analogues of the usual algebraic laws
for process combinators. We also show that quantitative
properties of interest are continuous with respect to the metric,
which says that if two processes are close in the metric then
observable quantitative properties of interest are indeed close.
As an important example of this we show that nearby processes have
nearby channel capacities - a quantitative measure of their
propensity to leak information.
© IEEE, 2002.
@InProceedings{weakmetric-lics02,
author = "Josee Desharnais and Vineet Gupta and Radha Jagadeesan and Prakash Panangaden",
title = "The Metric Analogue of Weak Bisimulation for Probabilistic Processes",
booktitle = "Proceedings of the Seventeenth Annual IEEE Symposium
on Logic in Computer Science",
year = "2002",
month = "July",
organization = "IEEE Computer Society Press"
}
Postscript file of extended abstract
Postscript file of full paper