文章基本信息

标题：Complete Axiomatization for the Bisimilarity Distance on Markov Chains
本地全文：下载
作者：Giorgio Bacci ; Giovanni Bacci ; Kim G. Larsen 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2016
卷号：59
页码：21:1-21:14
DOI：10.4230/LIPIcs.CONCUR.2016.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In this paper we propose a complete axiomatization of the bisimilarity distance of Desharnais et al. for the class of finite labelled Markov chains. Our axiomatization is given in the style of a quantitative extension of equational logic recently proposed by Mardare, Panangaden, and Plotkin (LICS'16) that uses equality relations t =_e s indexed by rationals, expressing that "t is approximately equal to s up to an error e". Notably, our quantitative deductive system extends in a natural way the equational system for probabilistic bisimilarity given by Stark and Smolka by introducing an axiom for dealing with the Kantorovich distance between probability distributions.
关键词：Markov chains; Behavioral distances; Axiomatization