Complete Axiomatization for the Total Variation Distance of Markov Chains

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

1 Citationer (Scopus)
132 Downloads (Pure)

Abstrakt

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).
OriginalsprogEngelsk
TidsskriftElectronic Notes in Theoretical Computer Science
Vol/bind336
Sider (fra-til)27-39
Antal sider13
ISSN1571-0661
DOI
StatusUdgivet - 16 apr. 2018
BegivenhedMathematical Foundations of Programming Semantics XXXIII - Faculty of Mathematics and Physics in Ljubljana, Ljubljana, Slovenien
Varighed: 12 jul. 201716 jul. 2017
http://coalg.org/mfps-calco2017/

Konference

KonferenceMathematical Foundations of Programming Semantics XXXIII
Lokation Faculty of Mathematics and Physics in Ljubljana
LandSlovenien
ByLjubljana
Periode12/07/201716/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

    Approximate Reasoning for Stochastic Markovian Systems

    Mardare, R. & Larsen, K. G.

    01/11/201531/10/2019

    Projekter: ProjektForskning

    Citationsformater