Complete axiomatization for the bisimilarity distance on Markov chains

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

doi:10.4230/LIPIcs.CONCUR.2016.21

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 proceeding › Conference contribution book

6 Citations (Scopus)

24 Downloads (Pure)

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 language	English
Title of host publication	27th International Conference on Concurrency Theory, CONCUR 2016
Editors	Josee Desharnais, Radha Jagadeesan
Number of pages	14
Volume	59
ISBN (Electronic)	9783959770170
DOIs	https://doi.org/10.4230/LIPIcs.CONCUR.2016.21
Publication status	Published - 1 Aug 2016
Event	27th International Conference on Concurrency Theory, CONCUR 2016 - Quebec City, Canada Duration: 23 Aug 2016 → 26 Aug 2016

Conference

Conference	27th International Conference on Concurrency Theory, CONCUR 2016
Country/Territory	Canada
City	Quebec City
Period	23/08/16 → 26/08/16

Keywords

axiomatization
behavioral distances
Markov chains
Markov processes
probability distributions
probabilistic bisimilarity

Access to Document

10.4230/LIPIcs.CONCUR.2016.21Licence: CC BY 4.0

Bacci-etal-CONCUR2016-Complete-axiomatization-bisimilarity-distance-Markov-chainsFinal published version, 588 KBLicence: CC BY 4.0

Cite this

@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 = aug,

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",

note = "27th International Conference on Concurrency Theory, CONCUR 2016 ; Conference date: 23-08-2016 Through 26-08-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

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

AN - SCOPUS:85012927224

VL - 59

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

A2 - Desharnais, Josee

A2 - Jagadeesan, Radha

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

Y2 - 23 August 2016 through 26 August 2016

ER -

Complete axiomatization for the bisimilarity distance on Markov chains

Abstract

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this