### Resumé

Originalsprog | Engelsk |
---|---|

Tidsskrift | Electronic Notes in Theoretical Computer Science |

Vol/bind | 336 |

Sider (fra-til) | 27-39 |

Antal sider | 13 |

ISSN | 1571-0661 |

DOI | |

Status | Udgivet - 16 apr. 2018 |

Begivenhed | Mathematical Foundations of Programming Semantics XXXIII - Faculty of Mathematics and Physics in Ljubljana, Ljubljana, Slovenien Varighed: 12 jul. 2017 → 16 jul. 2017 http://coalg.org/mfps-calco2017/ |

### Konference

Konference | Mathematical Foundations of Programming Semantics XXXIII |
---|---|

Lokation | Faculty of Mathematics and Physics in Ljubljana |

Land | Slovenien |

By | Ljubljana |

Periode | 12/07/2017 → 16/07/2017 |

Internetadresse |

### Fingerprint

### Citer dette

}

**Complete Axiomatization for the Total Variation Distance of Markov Chains.** / Bacci, Giorgio; Bacci, Giovanni; Larsen, Kim G.; Mardare, Radu.

Publikation: Bidrag til tidsskrift › Konferenceartikel i tidsskrift › Forskning › peer review

TY - GEN

T1 - Complete Axiomatization for the Total Variation Distance of Markov Chains

AU - Bacci, Giorgio

AU - Bacci, Giovanni

AU - Larsen, Kim G.

AU - Mardare, Radu

PY - 2018/4/16

Y1 - 2018/4/16

N2 - We propose a complete axiomatization for the total variation distance of finite labelled Markov chains. Our axiomatization is given in the form of a quantitative deduction system, a framework recently proposed by Mardare, Panangaden, and Plotkin (LICS 2016) to extend classical equational deduction systems by means of inferences of equality relations t =_e s indexed by rationals, expressing that “t is approximately equal to s up to an error e”. Notably, the quantitative equational system is obtained by extending our previous axiomatization (CONCUR 2016) for the probabilistic bisimilarity distance with a distributivity axiom for the prefix operator over the probabilistic choice inspired by Rabinovich's (MFPS 1983). Finally, we propose a metric extension to the Kleene-style representation theorem for finite labelled Markov chains w.r.t. trace equivalence due to Silva and Sokolova (MFPS 2011).

AB - We propose a complete axiomatization for the total variation distance of finite labelled Markov chains. Our axiomatization is given in the form of a quantitative deduction system, a framework recently proposed by Mardare, Panangaden, and Plotkin (LICS 2016) to extend classical equational deduction systems by means of inferences of equality relations t =_e s indexed by rationals, expressing that “t is approximately equal to s up to an error e”. Notably, the quantitative equational system is obtained by extending our previous axiomatization (CONCUR 2016) for the probabilistic bisimilarity distance with a distributivity axiom for the prefix operator over the probabilistic choice inspired by Rabinovich's (MFPS 1983). Finally, we propose a metric extension to the Kleene-style representation theorem for finite labelled Markov chains w.r.t. trace equivalence due to Silva and Sokolova (MFPS 2011).

KW - Axiomatization

KW - Behavioral Distances

KW - Markov Chains

KW - Quantitative Deductive Systems

U2 - 10.1016/j.entcs.2018.03.014

DO - 10.1016/j.entcs.2018.03.014

M3 - Conference article in Journal

VL - 336

SP - 27

EP - 39

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

SN - 1571-0661

ER -