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.