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 Kleenestyle 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 (fromto)  2739 
Number of pages  13 
ISSN  15710661 
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/mfpscalco2017/ 
Conference
Conference  Mathematical Foundations of Programming Semantics XXXIII 

Location  Faculty of Mathematics and Physics in Ljubljana 
Country/Territory  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

Approximate Reasoning for Stochastic Markovian Systems
Mardare, R. & Larsen, K. G.
01/11/2015 → 31/10/2019
Project: Research