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

2 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.

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

Fingerprint

Markov processes
Probability distributions

Keywords

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

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
Bacci, Giorgio ; Bacci, Giovanni ; Larsen, Kim G. ; Mardare, Radu. / Complete axiomatization for the bisimilarity distance on Markov chains. 27th International Conference on Concurrency Theory, CONCUR 2016. editor / Josee Desharnais ; Radha Jagadeesan. Vol. 59 2016.
@inproceedings{dcbe9ad0db77477cbd79bb867182be6e,
title = "Complete axiomatization for the bisimilarity distance on Markov chains",
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.",
keywords = "axiomatization, behavioral distances, Markov chains, Markov processes, probability distributions, probabilistic bisimilarity",
author = "Giorgio Bacci and Giovanni Bacci and Larsen, {Kim G.} and Radu Mardare",
year = "2016",
month = "8",
day = "1",
doi = "10.4230/LIPIcs.CONCUR.2016.21",
language = "English",
volume = "59",
editor = "Josee Desharnais and Radha Jagadeesan",
booktitle = "27th International Conference on Concurrency Theory, CONCUR 2016",

}

Bacci, G, Bacci, G, Larsen, KG & 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, 27th International Conference on Concurrency Theory, CONCUR 2016, Quebec City, Canada, 23/08/16. https://doi.org/10.4230/LIPIcs.CONCUR.2016.21

Complete axiomatization for the bisimilarity distance on Markov chains. / Bacci, Giorgio; Bacci, Giovanni; Larsen, Kim G.; Mardare, Radu.

27th International Conference on Concurrency Theory, CONCUR 2016. ed. / Josee Desharnais; Radha Jagadeesan. Vol. 59 2016. 21.

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

TY - GEN

T1 - Complete axiomatization for the bisimilarity distance on Markov chains

AU - Bacci, Giorgio

AU - Bacci, Giovanni

AU - Larsen, Kim G.

AU - Mardare, Radu

PY - 2016/8/1

Y1 - 2016/8/1

N2 - 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.

AB - 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.

KW - axiomatization

KW - behavioral distances

KW - Markov chains

KW - Markov processes

KW - probability distributions

KW - probabilistic bisimilarity

UR - http://www.scopus.com/inward/record.url?scp=85012927224&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.CONCUR.2016.21

DO - 10.4230/LIPIcs.CONCUR.2016.21

M3 - Conference contribution book

VL - 59

BT - 27th International Conference on Concurrency Theory, CONCUR 2016

A2 - Desharnais, Josee

A2 - Jagadeesan, Radha

ER -

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