Projekter pr. år
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).
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/Område | Slovenien |
By | Ljubljana |
Periode | 12/07/2017 → 16/07/2017 |
Internetadresse |
Fingeraftryk
Dyk ned i forskningsemnerne om 'Complete Axiomatization for the Total Variation Distance of Markov Chains'. Sammen danner de et unikt fingeraftryk.Projekter
- 1 Afsluttet
-
Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Projekter: Projekt › Forskning