Metrics for Labelled Markov Processes
Josee Desharnais, Vineet Gupta, Radha Jagadeesan, Prakash Panangaden
Abstract
The notion of process equivalence of probabilistic processes is sensitive to
the exact probabilities of transitions. Thus a slight change in the
transition probabilities will result in two equivalent processes being deemed
no longer equivalent. This instability is due to the quantitative nature of
probabilistic processes. In a situation where the process behaviour has a
quantitative aspect there should be a more robust approach to process
equivalence. This paper studies a metric between labelled Markov processes.
This metric has the property that processes are at zero distance if and only
if they are bisimilar. The metric is inspired by earlier work on logics for
characterizing bisimulation and is related, in spirit, to the Hutchinson
metric.
@InProceedings{metrics-concur99,
author = "Josee Desharnais and Vineet Gupta and Radha Jagadeesan and Prakash Panangaden",
title = "Metrics for Labelled Markov Processes",
journal = "Theoretical Computer Science",
notes = "To appear."
}
Postscript file.