An efficient algorithm to determine probabilistic bisimulation (Q2633253)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An efficient algorithm to determine probabilistic bisimulation |
scientific article |
Statements
An efficient algorithm to determine probabilistic bisimulation (English)
0 references
8 May 2019
0 references
Summary: We provide an algorithm to efficiently compute bisimulation for probabilistic labeled transition systems, featuring non-deterministic choice as well as discrete probabilistic choice. The algorithm is linear in the number of transitions and logarithmic in the number of states, distinguishing both action states and probabilistic states, and the transitions between them. The algorithm improves upon the proposed complexity bounds of the best algorithm addressing the same purpose so far by \textit{C. Baier} et al. [J. Comput. Syst. Sci. 60, No. 1, 187--231 (2000; Zbl 1073.68690)]. In addition, experimentally, on various benchmarks, our algorithm performs rather well; even on relatively small transition systems, a performance gain of a factor 10,000 can be achieved.
0 references
probabilistic system with nondeterminism
0 references
probabilistic labeled transition system
0 references
probabilistic bisimulation
0 references
partition-refinement algorithm
0 references
0 references
0 references