Complete axiomatization for the bisimilarity distance on Markov chains

Giorgio Bacci, Giovanni Bacci, Kim G. Larsen, Radu Mardare

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

3 Citations (Scopus)

Abstract

In this paper we propose a complete axiomatization of the bisimilarity distance of Desharnais et al. for the class of finite labelled Markov chains. Our axiomatization is given in the style of a quantitative extension of equational logic recently proposed by Mardare, Panangaden, and Plotkin (LICS'16) that uses equality relations t ϵ s indexed by rationals, expressing that "t is approximately equal to s up to an error ϵ. Notably, our quantitative deductive system extends in a natural way the equational system for probabilistic bisimilarity given by Stark and Smolka by introducing an axiom for dealing with the Kantorovich distance between probability distributions.

Original languageEnglish
Title of host publication27th International Conference on Concurrency Theory, CONCUR 2016
EditorsJosee Desharnais, Radha Jagadeesan
Number of pages14
Volume59
ISBN (Electronic)9783959770170
DOIs
Publication statusPublished - 1 Aug 2016
Event27th International Conference on Concurrency Theory, CONCUR 2016 - Quebec City, Canada
Duration: 23 Aug 201626 Aug 2016

Conference

Conference27th International Conference on Concurrency Theory, CONCUR 2016
CountryCanada
CityQuebec City
Period23/08/1626/08/16

Keywords

  • axiomatization
  • behavioral distances
  • Markov chains
  • Markov processes
  • probability distributions
  • probabilistic bisimilarity

Fingerprint Dive into the research topics of 'Complete axiomatization for the bisimilarity distance on Markov chains'. Together they form a unique fingerprint.

  • Cite this

    Bacci, G., Bacci, G., Larsen, K. G., & Mardare, R. (2016). Complete axiomatization for the bisimilarity distance on Markov chains. In J. Desharnais, & R. Jagadeesan (Eds.), 27th International Conference on Concurrency Theory, CONCUR 2016 (Vol. 59). [21] https://doi.org/10.4230/LIPIcs.CONCUR.2016.21