License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2017.27
URN: urn:nbn:de:0030-drops-77983
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7798/
Go to the corresponding LIPIcs Volume Portal

Tang, Qiyi ; van Breugel, Franck

Algorithms to Compute Probabilistic Bisimilarity Distances for Labelled Markov Chains

pdf-format:
LIPIcs-CONCUR-2017-27.pdf (0.5 MB)

Abstract

In the late nineties, Desharnais, Gupta, Jagadeesan and Panangaden presented probabilistic bisimilarity distances on the states of a labelled Markov chain. This provided a quantitative generalisation of probabilistic bisimilarity introduced by Larsen and Skou a decade earlier. In the last decade, several algorithms to approximate and compute these probabilistic bisimilarity distances have been put forward. In this paper, we correct, improve and generalise some of these algorithms. Furthermore, we compare their performance experimentally.

BibTeX - Entry

@InProceedings{tang_et_al:LIPIcs:2017:7798,
  author =	{Qiyi Tang and Franck van Breugel},
  title =	{{Algorithms to Compute Probabilistic Bisimilarity Distances for Labelled Markov Chains}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{27:1--27:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Roland Meyer and Uwe Nestmann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7798},
  URN =		{urn:nbn:de:0030-drops-77983},
  doi =		{10.4230/LIPIcs.CONCUR.2017.27},
  annote =	{Keywords: labelled Markov chain, probabilistic bisimilarity, pseudometric, policy iteration}
}

Keywords: labelled Markov chain, probabilistic bisimilarity, pseudometric, policy iteration
Collection: 28th International Conference on Concurrency Theory (CONCUR 2017)
Issue Date: 2017
Date of publication: 01.09.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI