Projects per year

### Abstract

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

Original language | English |
---|---|

Journal | Electronic Notes in Theoretical Computer Science |

Volume | 336 |

Pages (from-to) | 27-39 |

Number of pages | 13 |

ISSN | 1571-0661 |

DOIs | |

Publication status | Published - 16 Apr 2018 |

Event | Mathematical Foundations of Programming Semantics XXXIII - Faculty of Mathematics and Physics in Ljubljana, Ljubljana, Slovenia Duration: 12 Jul 2017 → 16 Jul 2017 http://coalg.org/mfps-calco2017/ |

### Conference

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

Location | Faculty of Mathematics and Physics in Ljubljana |

Country | Slovenia |

City | Ljubljana |

Period | 12/07/2017 → 16/07/2017 |

Internet address |

### Keywords

- Axiomatization
- Behavioral Distances
- Markov Chains
- Quantitative Deductive Systems

## Fingerprint Dive into the research topics of 'Complete Axiomatization for the Total Variation Distance of Markov Chains'. Together they form a unique fingerprint.

## Projects

- 1 Finished