2026-07-24T10:09:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3879 2024-03-06T10:34:35Z ddc:004 open_access

Deciding Probabilistic Automata Weak Bisimulation in Polynomial Time Hermanns, Holger Turrini, Andrea Probabilistic Automata Weak probabilsitic bisimulation Linear Programming problem Polynomial decision algorithm 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Holger Hermanns and Andrea Turrini 2012 Is Part Of LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2012.435 urn:nbn:de:0030-drops-38794 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.435 eng https://creativecommons.org/licenses/by-nc-nd/3.0/legalcode