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.2018.9
URN: urn:nbn:de:0030-drops-95472
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9547/
Go to the corresponding LIPIcs Volume Portal

Tang, Qiyi ; van Breugel, Franck

Deciding Probabilistic Bisimilarity Distance One for Probabilistic Automata

pdf-format:
LIPIcs-CONCUR-2018-9.pdf (0.4 MB)

Abstract

Probabilistic bisimilarity, due to Segala and Lynch, is an equivalence relation that captures which states of a probabilistic automaton behave exactly the same. Deng, Chothia, Palamidessi and Pang proposed a robust quantitative generalization of probabilistic bisimilarity. Their probabilistic bisimilarity distances of states of a probabilistic automaton capture the similarity of their behaviour. The smaller the distance, the more alike the states behave. In particular, states are probabilistic bisimilar if and only if their distance is zero.
Although the complexity of computing probabilistic bisimilarity distances for probabilistic automata has already been studied and shown to be in NP cap coNP and PPAD, we are not aware of any practical algorithm to compute those distances. In this paper we provide several key results towards algorithms to compute probabilistic bisimilarity distances for probabilistic automata. In particular, we present a polynomial time algorithm that decides distance one. Furthermore, we give an alternative characterization of the probabilistic bisimilarity distances as a basis for a policy iteration algorithm.

BibTeX - Entry

@InProceedings{tang_et_al:LIPIcs:2018:9547,
  author =	{Qiyi Tang and Franck van Breugel},
  title =	{{Deciding Probabilistic Bisimilarity Distance One for Probabilistic Automata}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9547},
  URN =		{urn:nbn:de:0030-drops-95472},
  doi =		{10.4230/LIPIcs.CONCUR.2018.9},
  annote =	{Keywords: probabilistic automaton, probabilistic bisimilarity, distance}
}

Keywords: probabilistic automaton, probabilistic bisimilarity, distance
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

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