2026-07-23T00:23:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6183 2024-03-06T10:38:29Z ddc:004 open_access

Computing Probabilistic Bisimilarity Distances via Policy Iteration Tang, Qiyi van Breugel, Franck labelled Markov chain simple stochastic game probabilistic bisimilarity pseudometric value function policy iteration A transformation mapping a labelled Markov chain to a simple stochastic game is presented. In the resulting simple stochastic game, each vertex corresponds to a pair of states of the labelled Markov chain. The value of a vertex of the simple stochastic game is shown to be equal to the probabilistic bisimilarity distance, a notion due to Desharnais, Gupta, Jagadeesan and Panangaden, of the corresponding pair of states of the labelled Markov chain. Bacci, Bacci, Larsen and Mardare introduced an algorithm to compute the probabilistic bisimilarity distances for a labelled Markov chain. A modification of a basic version of their algorithm for a labelled Markov chain is shown to be the policy iteration algorithm applied to the corresponding simple stochastic game. Furthermore, it is shown that this algorithm takes exponential time in the worst case. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Qiyi Tang and Franck van Breugel 2016 Is Part Of LIPIcs, Volume 59, 27th International Conference on Concurrency Theory (CONCUR 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2016.22 urn:nbn:de:0030-drops-61837 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2016.22 eng https://creativecommons.org/licenses/by/3.0/legalcode