License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2012.435
URN: urn:nbn:de:0030-drops-38794
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3879/
Go to the corresponding LIPIcs Volume Portal

Hermanns, Holger ; Turrini, Andrea

Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time

pdf-format:
40.pdf (0.7 MB)

Abstract

Deciding in an efficient way weak probabilistic bisimulation in the context of probabilistic automata is an open problem for about a decade. In this work we close this problem by proposing a procedure that checks in polynomial time the existence of a weak combined transition satisfying the step condition of the bisimulation. This enables us to arrive at a polynomial time algorithm for deciding weak probabilistic bisimulation. We also present several extensions to interesting related problems setting the ground for the development of more effective and compositional analysis algorithms for probabilistic systems.

BibTeX - Entry

@InProceedings{hermanns_et_al:LIPIcs:2012:3879,
  author =	{Holger Hermanns and Andrea Turrini},
  title =	{{Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) },
  pages =	{435--447},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{Deepak D'Souza and Telikepalli Kavitha and Jaikumar Radhakrishnan},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2012/3879},
  URN =		{urn:nbn:de:0030-drops-38794},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.435},
  annote =	{Keywords: Probabilistic Automata, Weak probabilsitic bisimulation, Linear Programming problem, Polynomial decision algorithm}
}

Keywords: Probabilistic Automata, Weak probabilsitic bisimulation, Linear Programming problem, Polynomial decision algorithm
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)
Issue Date: 2012
Date of publication: 14.12.2012

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